题目
Description
ZJ和ZCX在一起很久s了,两个人都互生爱意,最终决定喜结良缘,从此踏入浪漫的婚姻殿堂。
但是,ZJ的好基友们想到以后ZJ就不能经常跟他们一起愉快的玩耍了,都觉得非常伤心难过,于是他们决定在最后一晚为ZJ开一场单身晚会,玩整晚紧张刺激的飞行棋。
ZJ的好基友居住在城市的各个地方(每个地方不一定只有一个基友),他们需要从各个地方赶到其中一个朋友的家里来参加这最后的单身PARTY,ZJ被基友们的热情深深感动了,决定对基友们来时的路费进行报销。报销规则按照距离来计算。基友们为了帮ZJ省钱,决定在所有人走最短路径的情况下,总距离最小的人的家里开PARTY。
ZJ想知道基友们走过的总距离是多少,然后他把总共需要报销的钱拿出来,就可以让基友们自己来分配了。但是他算了半天也没算出来总距离是多少,单身PARTY马上就开始了,你能帮帮他吗?Input
第一行一个整数T,表示有T(T<15)组数据
每组数据的第一行基友数(包括ZJ)N(N<100),路口P(2<=P<=100),路口之间道路数C(1<=C<=1450),(基友的编号为1…N,路口的编号为1…P)
第二行到第N+1行:编号为1到N的基友们家所在的路口号。
第N+2行到N+C+1行:每行有三个数:相连的路口A,B,路口间间距D(1<=D<=255),当然,连接是双向的。Output
每组数据输出占一行,输出大家必须要走的最小距离和
Sample Input
1
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5Sample Output
8
题解
非常直白的模板题
题目叙述有误
在任意一个路口开晚会(可以在没有基友的路口开晚会),使所有基友的总路程最小
写的时候,Floyd算法写的有误
用于遍历i
和j
的途径点的k
应该在最外层循环
(在最内层会有问题)
即
for(int k = 1;k <= p;k++) for(int i = 1;i <= p;i++) for(int j = 1;j <= p;j++)
代码
/* By:OhYee Github:OhYee HomePage:http://www.oyohyee.com Email:oyohyee@oyohyee.com かしこいかわいい? エリーチカ! 要写出来Хорошо的代码哦~ */ #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <vector> #include <list> #include <set> #include <queue> #include <stack> #include <map> using namespace std; const int maxn = 105; const int maxc = 1455; const int INF = 999999999; int GayHome[maxn]; int Road[maxc][maxc]; void Do() { int n,p,c; scanf("%d%d%d",&n,&p,&c); for(int i = 1;i <= p;i++) for(int j = 1;j <= p;j++) Road[i][j] = INF; for(int i = 1;i <= n;i++) scanf("%d",&GayHome[i]); for(int i = 0;i < c;i++) { int a,b,d; scanf("%d%d%d",&a,&b,&d); Road[a][b] = Road[b][a] = d; } for(int i = 1;i <= p;i++) Road[i][i] = 0; for(int k = 1;k <= p;k++) for(int i = 1;i <= p;i++) for(int j = 1;j <= p;j++) Road[i][j] = min(Road[i][k] + Road[k][j],Road[i][j]); /*for(int i = 1;i <= p;i++) { for(int j = 1;j <= p;j++) printf("%5d ",Road[i][j]); printf("\n"); }*/ long long Min = INF; for(int i = 1;i <= p;i++) { long long sum = 0; for(int j = 1;j <= n;j++) { sum += Road[i][GayHome[j]]; } Min = min(Min,sum); } printf("%lld\n",Min); } int main() { int T; scanf("%d",&T); while(T--) Do(); return 0; }