不容易啊，真不容易啊。我在这题上大概卡了一年了吧。（其实是我一年没碰USACO的关系）
而且又是3.2的最后一题，又没办法绕过去……
恩，为了练习英语，所以把题目完整地翻译一下。
有一个叫John的农民，发现了一个制作在Wisconsin这个地方里最甜的奶油的秘密，那就是糖。他在牧草里放一些糖块，他知道他的N (1 <= N <= 500)头牛会去添这些加了糖的牧草，可以产出超级甜的奶油，能卖个好价钱。（……翻译题目真麻烦）
农民J很懒，但是他知道他可以训练他的奶牛，让他们在听到铃声之后前往一块特定的牧草场。他打算把加糖牧草放在那块牧草场上，在下午摇铃铛，这样在晚上就可以收获超级甜的奶油了。
农民J知道每头奶牛都会在话费一些时间去牧草场。现在给你一幅牧草场以及连接他们之间的路线的图，希望你能找出一块牧场，若农民J在这块牧场上防止加糖牧草，在摇铃时所有奶牛的行走路线之和最小。农民J知道他的牧场都是联通的，所以此题一定会有解。
程序名称: butter
输入格式
*第2行：三个由空格分开的数字：N，牧草场的总数量P (2 <= P <= 800)，以及道路的总数量C (1 <= C <= 1,450 )。每头奶牛都有唯一编号 1..N。道路也有唯一编号 1..P。
*第2至N+1行：每一行有单独的一个数字，表示在这个牧场里有一头奶牛。在第i+1行列出奶牛i的位置。
*第N+2至第N+C+1行：每一行都有三个数字表示一条连接两个牧场的道路，以及他的长度。道路没有方向。任何两个牧场之间的道路数量不会大于1。前两个数字范围是1..P；第三个数字范围是1..225。
样例输入 (file butter.in)
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
样例输出 (file butter.out)
8
好吧。
其实是求图中某一个结点，所有其他结点到这个结点的加权最短路径之和最短。
我一年前是用Floyd做的。虽然我也知道Floyd O(n^3)必然会超时，但是还是希望在Floyd基础上优化一下然后AC之。
结果还是TLE。
好吧，其实我早就知道这题应该用Heap+Dijk做的。只是一直懒得写
或者，不敢写。
因为我最终写出来的代码竟然丑陋成这个样子！
/*
ID: 4everma1
LANG: C++
PROG: butter
*/
#include <iostream>
#include <fstream>
#define P 800
#define C 1450
#define MAX 9999
using namespace std;
#define READ_FROM_FILE
int heap[P];
//heap是堆
int heapLength;
int hash[P];
//hash[i]为第i个点在堆中的位置
int map[P][P];
int edgeNumber[P];
int edge[P][C];
void swap(int* a,int* b)
{
int x=*a;
*a=*b;
*b=x;
return;
}
void repair(int* heap,int nowNode,int node)
{
int l=node;
while(l>0)
{
if(map[nowNode][heap[(l-1)/2]]>map[nowNode][heap[l]])
{
swap(&hash[heap[(l-1)/2]],&hash[heap[l]]);
swap(&heap[(l-1)/2],&heap[l]);
l=(l-1)/2;
}
else
{
break;
}
}
}
void insert(int* heap,int nowNode,int node)
{
int l=heapLength;
hash[node]=l;
heap[heapLength++]=node;
repair(heap,nowNode,l);
return;
}
int extract(int* heap,int nowNode)
{
int ans=heap[0];
heap[0]=heap[heapLength-1];
heapLength--;
int now=0;
int left;
int right;
while(true)
{
left=(now+1)*2-1;
right=left+1;
if(left>heapLength)
break;
if(right>heapLength)
{
//比较结点与左儿子的大小
if(map[nowNode][heap[now]]>map[nowNode][heap[left]])
{
swap(&hash[heap[now]],&hash[heap[left]]);
swap(&heap[now],&heap[left]);
now=left;
}
else
{
break;
}
}
else
{
left=map[nowNode][heap[left]]>map[nowNode][heap[right]]?right:left;
if(map[nowNode][heap[now]]>map[nowNode][heap[left]])
{
swap(&hash[heap[now]],&hash[heap[left]]);
swap(&heap[now],&heap[left]);
now=left;
}
else
{
break;
}
}
}
return(ans);
}
main()
{
int n,p,c;
int i,j,k,t;
int hasCow[P];
int in[P];
#ifdef READ_FROM_FILE
ifstream cin ("butter.in");
ofstream cout ("butter.out");
#endif
//读入数据
cin>>n>>p>>c;
//初始化
for(i=0;i<p;i++)
{
for(j=0;j<p;j++)
{
map[i][j]=MAX;
}
hasCow[i]=0;
edgeNumber[i]=0;
}
for(i=0;i<n;i++)
{
cin>>t;
hasCow[--t]++;
}
for(i=0;i<c;i++)
{
cin>>j>>k>>t;
map[j-1][k-1]=map[k-1][j-1]=t;
edge[j-1][edgeNumber[j-1]++]=k-1;
edge[k-1][edgeNumber[k-1]++]=j-1;
}
//对于每个点，用heap+dijk求出到每个点的最短路径
for(i=0;i<p;i++)
{
//初始化堆
heapLength=0;
for(j=0;j<p;j++)
{
in[j]=0;
if(i!=j)
insert(heap,i,j);
}
in[i]=1;
while(heapLength>0)
{
int u=extract(heap,i);
//从堆中找到距离i最近的点u
in[u]=1;
int d=map[i][u];
//d是i到u的最短距离
//for(j=0;j<p;j++)
for(k=0;k<edgeNumber[u];k++)
{
j=edge[u][k];
if(in[j]==1)
continue;
if(map[j][u]+d<map[i][j])
{
map[i][j]=map[j][u]+d;
//更新i到j的距离
repair(heap,i,hash[j]);
//在堆中修改j所对应的值
}
}
//求出所有点到点i的最短路径
}
}
//遍历图，求出答案
int ans=0;
for(i=0;i<p;i++)
{
int tans=0;
for(j=0;j<p;j++)
{
if(i!=j)
tans+=hasCow[j]*map[j][i];
}
if(ans==0||tans<ans)
{
ans=tans;
}
}
cout<<ans<<endl;
#ifdef READ_FROM_FILE
cin.close();
cout.close();
#endif
}
USER: MaxWell Z [4everma1]
TASK: butter
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 10056 KB]
Test 2: TEST OK [0.011 secs, 10056 KB]
Test 3: TEST OK [0.022 secs, 10056 KB]
Test 4: TEST OK [0.011 secs, 10056 KB]
Test 5: TEST OK [0.011 secs, 10056 KB]
Test 6: TEST OK [0.032 secs, 10056 KB]
Test 7: TEST OK [0.108 secs, 10056 KB]
Test 8: TEST OK [0.216 secs, 10056 KB]
Test 9: TEST OK [0.378 secs, 10056 KB]
Test 10: TEST OK [0.367 secs, 10056 KB]
All tests OK.
Your program ('butter') produced all correct answers! This is your submission #75 for this problem. Congratulations!
看到了没有，75次啊！！整整灭了75次啊！！
今天晚上大概灭了20来次。
前几次是Heap和Dijk写错。
然后后来还是TLE，看了一下发现C
恩，这标志着3.2时代的结束。
明天开始就是3.3了。
（不知道USACO有没有LK这样的BOSS=。=）
不对……等一下……
3.3好象是……欧拉回路？
期待してたのに...
