【题解-洛谷】P2935 [USACO09JAN] Best Spot S
题目：P2935 [USACO09JAN] Best Spot S
题目描述
约翰拥有 P ( 1 ≤ P ≤ 500 ) P(1 \leq P \leq 500) P(1≤P≤500) 个牧场，
贝茜特别喜欢其中的 F ( 1 ≤ F ≤ P ) F(1\leq F \leq P) F(1≤F≤P) 个。
所有的牧场由 C ( 1 < C ≤ 8000 ) C(1 < C \leq 8000) C(1<C≤8000) 条双向路连接，第 i i i 条路连接着 a i a_i ai, b i b_i bi 两个牧场 ( 1 ≤ a i ≤ P , 1 ≤ b i ≤ P ) (1 \leq a_i \leq P,1 \leq b_i \leq P) (1≤ai≤P,1≤bi≤P)，需要 T i ( 1 ≤ T i < 892 ) T_i(1 \leq T_i < 892) Ti(1≤Ti<892) 个单位时间来通过。
作为一只总想提升自己生活方式的奶牛，贝茜希望自己有朝一日醒来，到达所有那 F F F 个她喜欢的牧场的平均用时最小。那她前一天应该睡在哪个牧场呢？请帮助贝茜找到这个最佳牧场。
例如，考虑如下图所示的牧场布局，其中含有 * 的牧场的编号是最受欢迎的。而中括号内的数字是这条牛道的通过时间。
1*--[4]--2--[2]--3| |[3] [4]| |4--[3]--5--[1]---6---[6]---7--[7]--8*| | | |[3] [2] [1] [3]| | | |13* 9--[3]--10*--[1]--11*--[3]--12*
下表显示了牧场 4 , 5 , 6 , 7 , 9 , 10 , 11 4,5,6,7,9,10,11 4,5,6,7,9,10,11 和 12 12 12 的与“最佳牧场”的各个距离、平均距离和最佳牧场：
* * * * * * 最喜欢的牧场 * * * * * *可能的 牧场 牧场 牧场 牧场 牧场 牧场 平均最佳牧场 1 8 10 11 12 13 距离
------------ -- -- -- -- -- -- -----------4 7 16 5 6 9 3 46/6 = 7.675 10 13 2 3 6 6 40/6 = 6.676 11 12 1 2 5 7 38/6 = 6.337 16 7 4 3 6 12 48/6 = 8.009 12 14 3 4 7 8 48/6 = 8.0010 12 11 0 1 4 8 36/6 = 6.00 ** 最佳的11 13 10 1 0 3 9 36/6 = 6.0012 16 13 4 3 0 12 48/6 = 8.00由表格可见，在样例环境下，牧场 10 10 10 到所有贝茜喜欢的牧场的平均距离最小，为最佳牧场。
输入格式
第一行包含三个整数 P P P, F F F, C C C。
接下来 F F F 行，每行一个整数，表示贝茜喜欢的牧场的编号。
接下来 C C C 行，每行三个整数 a i a_i ai, b i b_i bi, T i T_i Ti，表示存在一条连接 a i a_i ai 和 b i b_i bi 的双向通路，通过时间为 T i T_i Ti。
输出格式
一个整数，表示最佳的牧场编号。如果有多个最佳牧场，则输出编号最小的那一个。
输入输出样例 #1
输入 #1
13 6 15
11
13
10
12
8
1
2 4 3
7 11 3
10 11 1
4 13 3
9 10 3
2 3 2
3 5 4
5 9 2
6 7 6
5 6 1
1 2 4
4 5 3
11 12 3
6 10 1
7 8 7
输出 #1
10
说明/提示
翻译来自 AASDFGHJKL(1035916)。
代码
#include<iostream>using namespace std;const int MaxP = 500 + 10, INF = 1e9;int P, F, C, dist[MaxP][MaxP], fav[MaxP];void floyd(){for(int t = 1; t <= P; t ++){for(int i = 1; i <= P; i ++){for(int j = 1; j <= P; j ++){dist[i][j] = min(dist[i][j], dist[i][t] + dist[t][j]);}}}
}int main(){cin >> P >> F >> C;for(int i = 1; i <= F; i ++){cin >> fav[i];}for(int i = 1; i <= P; i ++){for(int j = 1; j <= P; j ++){if(i == j){dist[i][j] = 0;}else{dist[i][j] = INF;}}}while(C --){int a, b, w;cin >> a >> b >> w;dist[a][b] = dist[b][a] = min(dist[b][a], w);}floyd();int sum = 1e9, id = 0;for(int i = 1; i <= P; i ++){int ans = 0;for(int j = 1; j <= F; j ++){ans += dist[i][fav[j]];}if(ans < sum){sum = ans;id = i;}}cout << id;return 0;
}
结果
