The 2019 Asia Nanchang First Round Online Programming Contest B

Nanchang First Round Online Programming Contest B"/>

The 2019 Asia Nanchang First Round Online Programming Contest B

这道题的题意真的是……读吐了。
有V个点，其中hero在S点，另有K个救火队员分布在K个点。现在给你这个图（联通且无向），请你比较hero和队员的Value。Value：从当前点到其余V-1个点的最短路长度中的最大值。比如，对于hero，只有1个点，所以就是它自己到其余V-1个点的最短路中的最大值。
但是，对于队员们，我们对每个队员，是有V-1个最短路，但并不能直接在这V-1中取最大，之后再在K个中取最大。而是应该对V个点，每个点比较距离K个消防队员的距离，取最小值。最后在这K个值中取最大值。这个最大值才是消防队的Value。

就很恶心…还有要注意的是，最后hero/C的时候可能会有问题，可以把C乘到另一边作比较。

（P.S.最开始写的dijskra，一直WA，队友来了接过去重写用的floyd，最后在他的基础上改了好久过了，事后实验室的同学都很震惊floyd居然没被卡……

#include<bits/stdc++.h>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
//#define vec vector<vector<ll> >
using namespace std;
#define MAX_N 500010
#define ll long long
int d[1005][1005];
int team[1005];
int main()
{int T,V,E,S,K,C;int I, J,X;int ans;scanf("%d", &T);while (T--){memset(d, INF, sizeof(d));scanf("%d %d %d %d %d", &V, &E, &S, &K, &C);for (int i = 0; i < K; i++){scanf("%d", &team[i]);team[i]--;}for (int i = 0; i <E; i++){scanf("%d %d %d", &I, &J, &X);I--;J--;if (X < d[I][J]){d[I][J] = d[J][I] = X;}}for (int i = 0; i < V; i++){d[i][i] = 0;}for (int k = 0; k < V; k++){for (int i = 0; i < V; i++){for (int j = 0; j < V; j++){d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}//for(int i = 0;i < K;i++)//printf("%d\n", d[team[i]][team[i]]);int maxN = 0;int minN = INF;for (int i = 0; i < V; i++){minN = INF;for (int j = 0; j < K; j++)minN = min(d[i][team[j]], minN);if (minN != INF)maxN = max(minN, maxN);}ans = 0;for (int i = 0; i < V; i++){if (d[S - 1][i]!=INF)ans = max(ans, d[S - 1][i]);}if (ans > maxN * C)ans = maxN;printf("%d\n", ans);}
}