60分求助

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, int> pli;
const int N = 100005;
const int M = 500005;
const ll INF = 1e18;

struct Edge {
    int to, nxt;
    ll w;
} e[M];

int head[N], cnt;
int n, m, k;
int a[N]; 
int from[M], to[M];
ll w[M];
ll dis[N];
bool vis[N];
ll ans;

void init() {
    cnt = 0;
    memset(head, -1, sizeof(head));
}

void add(int u, int v, ll w) {
    e[cnt].to = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt ++;
}

void dijkstra(vector<int>& src) {
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        vis[i] = false;
    }
    for (int x : src) {
        if (x != -1) {
            dis[x] = 0;
            pq.push({0, x});
        }
    }
    
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                pq.push({dis[v], v});
            }
        }
    }
}

void solve() {
    scanf("%d%d%d", &n, &m, &k);
    
    // 读入边
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%lld", &from[i], &to[i], &w[i]);
    }
    
    // 读入特殊点
    for (int i = 0; i < k; i++) {
        scanf("%d", &a[i]);
    }
    
    ans = INF;
    
    // 二进制分组
    for (int bit = 0; bit <= 20; bit ++) {
        init();
        for (int i = 1; i <= m; i++) add(from[i], to[i], w[i]);
        
        vector<int> src;
        for (int i = 0; i < k; i ++) {
            if (!(i >> bit & 1)) src.push_back(a[i]);
            else src.push_back(-1);
        }
        dijkstra(src);
        
        for (int i = 0; i < k; i ++) {
            if ((i >> bit & 1) && dis[a[i]] < ans) {
                ans = min(ans, dis[a[i]]);
            }
        }
        
        init();
        for (int i = 1; i <= m; i ++) add(to[i], from[i], w[i]);
        
        src.clear();
        for (int i = 0; i < k; i ++) {
            if ((i >> bit & 1)) src.push_back(a[i]);
            else src.push_back(-1);
        }
        dijkstra(src);
        
        for (int i = 0; i < k; i ++) {
            if (!(i >> bit & 1) && dis[a[i]] < ans) {
                ans = min(ans, dis[a[i]]);
            }
        }
    }
    
    printf("%lld\n", ans);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T --) {
        solve();
    }
    return 0;
}