1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
| #include <bits/stdc++.h> #define memset0(x, s) memset(x, 0, sizeof(int) * (s + 2)) #define next \ ___________________________________________________________________________________________________ using namespace std;
typedef long long ll; const int MAXN = 100005, MAXM = 500005; const ll INF = 1ll << 60;
struct Edge { int u, to, next; ll w; } edge[MAXM << 1];
struct node { int id; ll dis; node(int tid, ll tdis) { id = tid; dis = tdis; } bool operator<(const node &B) const { return dis > B.dis; } };
ll dis1[MAXN], dis2[MAXN], ans; int head1[MAXN], head2[MAXN], id[MAXN], from1[MAXN], from2[MAXN], n, m, k, tot; bool vis[MAXN];
inline void addedge1(int u, int v, ll w) { edge[++tot] = (Edge){u, v, head1[u], w}, head1[u] = tot; }
inline void addedge2(int u, int v, ll w) { edge[++tot] = (Edge){u, v, head2[u], w}, head2[u] = tot; }
void dij1() { priority_queue<node> q; while (!q.empty()) q.pop(); for (int i = 1; i <= n; i++) dis1[i] = INF, vis[i] = 0; for (int i = 1; i <= k; i++) dis1[id[i]] = 0ll, from1[id[i]] = id[i], q.push(node(id[i], 0ll)); while (!q.empty()) { node cur = q.top(); q.pop(); int u = cur.id; if (vis[u]) continue; vis[u] = 1; for (int e = head1[u]; e; e = edge[e].next) { int v = edge[e].to; if (dis1[v] > dis1[u] + edge[e].w) dis1[v] = dis1[u] + edge[e].w, from1[v] = from1[u], q.push(node(v, dis1[v])); } } }
void dij2() { priority_queue<node> q; while (!q.empty()) q.pop(); for (int i = 1; i <= n; i++) dis2[i] = INF, vis[i] = 0; for (int i = 1; i <= k; i++) dis2[id[i]] = 0ll, from2[id[i]] = id[i], q.push(node(id[i], 0ll)); while (!q.empty()) { node cur = q.top(); q.pop(); int u = cur.id; if (vis[u]) continue; vis[u] = 1; for (int e = head2[u]; e; e = edge[e].next) { int v = edge[e].to; if (dis2[v] > dis2[u] + edge[e].w) dis2[v] = dis2[u] + edge[e].w, from2[v] = from2[u], q.push(node(v, dis2[v])); } } }
int main() { int T; scanf("%d", &T); for (; T; --T) { memset0(head1, n), memset0(head2, n), memset0(edge, m << 1), tot = 0, ans = INF, scanf("%d%d%d", &n, &m, &k); ll w; for (int i = 1, u, v; i <= m; i++) scanf("%d%d%lld", &u, &v, &w), addedge1(u, v, w), addedge2(v, u, w); for (int i = 1; i <= k; i++) scanf("%d", id + i); dij1(), dij2(); for (int i = 1; i <= m << 1; i += 2) { int u = edge[i].u, v = edge[i].to; ll w = edge[i].w; if (from1[u] != from2[v]) ans = min(ans, dis1[u] + w + dis2[v]); } printf("%lld\n", ans); } return 0; }
|