感觉是dijkstra函数有锅,可能死循环了
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
int n, m, k, ans;
bool go[MAXN], vis[MAXN];
struct edge {
int v, w;
};
struct node {
vector < edge > e;
int u, dis;
bool operator > (const node& a) const {
return a.dis > dis;
}
} g[MAXN];
void dijkstra(bool Harry, int begin) {
for (int i = 1; i <= n; i++)
g[i].dis = INT_MAX, vis[i] = false;
priority_queue < node, vector < node >, greater < node > > q;
g[begin].dis = 0;
q.push(g[begin]);
while (!q.empty()) {
int u = q.top().u, dis = q.top().dis;
vector < edge > e = q.top().e;
q.pop();
vis[u] = true;
for (edge ed : e)
if (!vis[ed.v] && (Harry || !go[ed.v]))
g[ed.v].dis = dis + ed.w, q.push(g[ed.v]);
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
while (k--) {
int snake;
scanf("%d", &snake);
go[snake] = true;
}
while (m--) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a].e.push_back({ b, c }), g[b].e.push_back({ a, c });
}
g[1].dis = 0;
int x, y;
scanf("%d%d", &x, &y);
dijkstra(true, 1);
int num1 = g[x].dis, num2 = g[y].dis;
ans = max(num1, num2);
dijkstra(false, 1);
ans = min(ans, max(g[y].dis, g[x].dis));
dijkstra(true, x);
ans = min(ans, min(num1, num2) + g[y].dis);
printf("%d", ans);
return 0;
}