题目

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 5

Sample 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;
}