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
| #include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int T;
int n, m, k;
int head[N], nxt[N], to[N], len[N], e_tot;
int x[N], y[N], z[N];
int imp[N];
void link(int x, int y, int z) {
nxt[++e_tot] = head[x], head[x] = e_tot, to[e_tot] = y, len[e_tot] = z;
}
int dis[3][N], vis[N];
priority_queue<pair<int, int> > q;
void spfa(int *dis, int S) {
for (int i = 0; i <= n + 2; ++i) dis[i] = 0x3f3f3f3f3f3f3f3f, vis[i] = 0;
q.push(make_pair(0, S));
dis[S] = 0;
while (q.size()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if (dis[v] > dis[u] + len[i]) {
dis[v] = dis[u] + len[i];
q.push(make_pair(-dis[v], v));
}
}
}
}
signed main() {
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld%lld", &n, &m, &k);
for (int i = 1; i <= m; ++i) {
scanf("%lld%lld%lld", &x[i], &y[i], &z[i]);
}
for (int i = 1; i <= k; ++i) {
scanf("%lld", &imp[i]);
}
int ans = 0;
int Min = 0x3f3f3f3f3f3f3f3f;
for (int i = 1; (1 << i - 1) <= k; ++i) {
memset(head, 0, sizeof(head));
memset(nxt, 0, sizeof(nxt));
e_tot = 0;
for (int j = 1; j <= k; ++j) {
if (j & (1 << i - 1)) {
link(n + 1, imp[j], 0);
}
else link(imp[j], n + 2, 0);
}
for (int j = 1; j <= m; ++j) {
link(x[j], y[j], z[j]);
}
spfa(dis[1], n + 1);
memset(head, 0, sizeof(head));
memset(nxt, 0, sizeof(nxt));
e_tot = 0;
for (int j = 1; j <= k; ++j) {
if (j & (1 << i - 1)) {
link(imp[j], n + 1, 0);
}
else link(n + 2, imp[j], 0);
}
for (int j = 1; j <= m; ++j) {
link(x[j], y[j], z[j]);
}
spfa(dis[2], n + 2);
Min = min(Min, dis[1][n + 2]);
Min = min(Min, dis[2][n + 1]);
}
cout << Min << endl;
}
return 0;
}
|