记录编号	601121	评测结果	AAAAAAAAAAAA
题目名称	3109.[GXOI/GZOI2019]旅行者	最终得分	100
用户昵称	wdsjl	是否通过	通过
代码语言	C++	运行时间	11.947 s
提交时间	2025-06-03 11:35:12	内存使用	7.38 MiB

#include <vector>
#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 7e5 + 10;

struct E {
    int t, w, n;
};

E es[M];
int h[N], bh[N], idx;

void ae(int u, int v, int w) {
    es[idx] = {v, w, h[u]};
    h[u] = idx++;
}

int n, nd[N], k, S, T;
long long d[N];

long long dj() {
    memset(d, 0x3f, sizeof(d));
    d[S] = 0;
    priority_queue<pair<long long, int>> q;
    q.push({0, S});
    for (int i = 1; i < n + 2; i++) {
        while (!q.empty() && d[q.top().second] != -q.top().first) q.pop();
        if (q.empty()) break;
        int u = q.top().second;
        q.pop();
        for (int i = h[u]; ~i; i = es[i].n)
            if (d[es[i].t] > d[u] + es[i].w)
                q.push({-(d[es[i].t] = d[u] + es[i].w), es[i].t});
    }
    return d[T];
}

int main() {
	freopen("WAW.in","r",stdin);
	freopen("WAW.out","w",stdout); 
    int t;
    scanf("%d", &t);
    while (t--) {
        idx = 0;
        memset(h, -1, sizeof(h));
        int m;
        scanf("%d%d%d", &n, &m, &k);
        while (m--) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            ae(u, v, w);
        }
        for (int i = 1; i <= k; i++) scanf("%d", nd + i);

        long long ans = ~0ull >> 1;
        S = n + 1, T = n + 2;
        for (int i = 0; (1 << i) <= k; i++) {
            int bidx = idx;
            memcpy(bh, h, sizeof(h));
            for (int j = 1; j <= k; j++)
                if (j & (1 << i)) ae(S, nd[j], 0);
                else ae(nd[j], T, 0);
            ans = min(ans, dj());
            idx = bidx;
            memcpy(h, bh, sizeof(h));
            for (int j = 1; j <= k; j++)
                if (j & (1 << i)) ae(nd[j], T, 0);
                else ae(S, nd[j], 0);
            ans = min(ans, dj());
            idx = bidx;
            memcpy(h, bh, sizeof(h));
        }
        printf("%lld\n", ans);
    }
    return 0;
}