英雄灭火问题忽略了一点丫
一个超级源点的事情,需要考虑周全丫
2
#include<cstdio> #include<cstring> #include<queue> #include<vector> #include<iostream> #include<algorithm> using namespace std; #define maxn 1010 #define INF 0x3f3f3f3f int T, n, m, s, k, c; struct Node { int p; int val; Node(int _p, int _val) :p(_p), val(_val) {} }; vector<Node>G[maxn]; void insert(int be, int en, int len) { G[be].push_back(Node(en, len)); } int dis[maxn]; int vis[maxn]; int spfa(int be) { queue<int>que; memset(vis, 0, sizeof(vis)); memset(dis, INF, sizeof(dis)); que.push(be); dis[be] = 0; while (!que.empty()) { int x = que.front(); que.pop(); vis[x] = 0; for (int i = 0; i < G[x].size(); i++) { int p = G[x][i].p; if (dis[p] > dis[x] + G[x][i].val) { dis[p] = dis[x] + G[x][i].val; if (!vis[p]) { que.push(p); vis[p] = 1; } } } } return 0; } int be, en, len; int main() { scanf("%d", &T); while (T--) { for (int i = 0; i < maxn - 2; i++) G[i].clear(); scanf("%d%d%d%d%d", &n, &m, &s, &k, &c); for (int i = 0; i < k; i++) { scanf("%d", &be); insert(0, be, 0); } for (int i = 0; i < m; i++) { scanf("%d %d %d", &be, &en, &len); insert(be, en, len); insert(en, be, len); } spfa(0); int ans1 = 0; for (int i = 1; i <= n; i++) { ans1 = max(ans1, dis[i]); } int ans2 = 0; spfa(s); for (int i = 1; i <= n; i++) { ans2 = max(ans2, dis[i]); } if (ans1*c >= ans2) printf("%d\n", ans2); else printf("%d\n", ans1); } return 0; }
我老婆