Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。
农夫John很狡猾。像以前的Pavlov，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛
到达的路程和最短的牧场（他将把糖放在那）
【输入格式】
第一行: 三个数：奶牛数N，牧场数（2<=P<=800），牧场间道路数C(1<=C<=1450)
第二行到第N+1行: 1到N头奶牛所在的牧场号
第N+2行到第N+C+1行： 每行有三个数：相连的牧场A、B，两牧场间距离D（1<=D<=255），当然,连接是双向的
【输出格式】
一行 输出奶牛必须行走的最小的距离和
Sample Input
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
{样例图形
P2
P1 @--1--@ C1
|
|
5 7 3
|
| C3
C2 @--5--@
P3 P4
}
【题解】
対每个点都进行一次spfa。牛从各个牛场到某个牛场的过程，可以看成是多头牛从一个牛场分别走回各自的牛场。所走过的距离是一样的。
进行多次spfa，然后记录下每个牛场的牛的数目。在每个牛场进行的spfa获得的dis数组用于累加所有牛走过的总距离。枚举每个牛场，获得这个总距离的最小值即可。最后输出。
初值设置成-1， 便于进行判断这个牛场是否为无穷大。
【代码】
#include <cstdio> #include <cstring> int n,p,c,a[900][900],w[900][900],num[900],dis[900],team[20000],mins = -1; bool exsit[1000]; void input_data() { scanf("%d%d%d",&n,&p,&c); //n是牛的总数。p是牛场的数目。C是道路数 for (int i = 1;i <= n;i++) { int x; scanf("%d",&x); num[x]++; } for (int i = 1;i <= c;i++) //输入n条路 { int x0,y0,z0; scanf("%d%d%d",&x0,&y0,&z0); //因为是无向图，所以要两边的出度都增加都记录。 a[x0][0]++; a[x0][a[x0][0]] = y0; w[x0][y0] = z0; a[y0][0]++; a[y0][a[y0][0]] = x0; w[y0][x0] = z0; } } void nspfa() { for (int i =1 ;i <= p;i++) //枚举放奶糖的牛场编号。 { memset(exsit,false,sizeof(exsit)); //一开始所有的牛场都不在队列中 for (int j = 1;j <= p;j++) dis[j] = -1; dis[i] = 0; //假设从第i号牛场进行spfa exsit[i] = true; team[1] = i; //把i加入队列 int head = 0,tail = 1; while (head != tail) { head++; head = ((head - 1) % 19000) + 1; //用循环队列 int f = team[head]; exsit[f] = false; for (int j = 1;j <= a[f][0];j++) { int t = a[f][j]; //f是起点 t是终点 if (dis[t] == -1 || dis[t] > dis[f] + w[f][t]) //如果能更新更优解则更新 { //-1代表正无穷。 dis[t] = dis[f] + w[f][t]; if (!exsit[t]) //如果终点不在队列中 则加入队列。 { exsit[t] = true; tail++; tail = ((tail-1) % 19000) + 1; team[tail] = t; } } } } int sum = 0; for (int j = 1;j <= p;j++) //直接累加，不用判断是不是起点（起点为0) sum+= num[j]*dis[j]; if (mins == -1) mins = sum; else if (sum < mins) mins = sum; } } void output_ans() { printf("%d ",mins); } int main() { //freopen("F:\rush.txt","r",stdin); input_data(); nspfa(); output_ans(); return 0; }