题目链接:https://syzoj.com/problem/291
内存限制：128 MiB 时间限制：1000 ms

题目描述

农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。 农夫John很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。 农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

输入格式

第一行: 三个数：奶牛数N，牧场数P（2<=P<=800），牧场间道路数C(1<=C<=1450)。 第二行到第N+1行: 1到N头奶牛所在的牧场号。 第N+2行到第N+C+1行：每行有三个数：相连的牧场A、B，两牧场间距（1<=D<=255），当然，连接是双向的。

输出格式

一行 输出奶牛必须行走的最小的距离和.

样例输入

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

样例输出

8

提示

样例图形
         P2  
P1 @--1--@ C1
    \    |\
     \   | \
      5  7  3
       \ |   \
        \|    \ C3
      C2 @--5--@
         P3    P4

//说明：放在4号牧场最优

解题思路

先算出牧场两两之间的最短路径，然后枚举每个牧场到其它牧场的距离相加，求出最小值。

#include <bits/stdc++.h>
using namespace std;
struct edge {
    int u, v, w;
}e[2905];
int cnt, s[805], f[805], vis[805], dis[805];
void Add(int u, int v, int w) {
    e[++cnt] = (edge){f[u], v, w};
    f[u] = cnt;
}
void Spfa(int s) {
    queue <int> Q;
    Q.push(s);
    dis[s] = 0;
    vis[s] = 1;
    while (!Q.empty()) {
        int t = Q.front();
        Q.pop();
        vis[t] = 0;
        for (int i = f[t]; i; i = e[i].u) {
            int v = e[i].v;
            if (dis[v] > dis[t] + e[i].w) {
                dis[v] = dis[t] + e[i].w;
                if (!vis[v]) {
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main() {
    int n, m, p, u, v, w, ans, min_s;
    while (~scanf("%d%d%d", &n, &m, &p)) {
        cnt = 0;
        min_s = 0x3f3f3f3f;
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; i++)
            scanf("%d", &s[i]);
        for (int i = 0; i < p; i++) {
            scanf("%d%d%d", &u, &v, &w);
            Add(u, v, w);
            Add(v, u, w);
        }
        for (int i = 1; i <= m; i++) {
            memset(vis, 0, sizeof(vis));
            memset(dis, 0x3f, sizeof(dis));
            Spfa(i);
            ans = 0;
            for (int j = 1; j <= n; j++)
                ans += dis[s[j]];
            min_s = min(ans, min_s);
        }
        printf("%d\n", min_s);
    }
    return 0;
}