题解 | #牛客春招刷题训练营#小红送外卖

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

const int maxn = 2e6 + 10;

typedef pair<long long, long long> PII;

int n, m, q;
int h[maxn], w[maxn], e[maxn], ne[maxn], idx;
long long dis[maxn];
bool st[maxn];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra() {
    for (int i = 0; i <= n + 3; i++) {
        dis[i] = 1e18;
        st[i] = false;
    }
    dis[1] = 0;
    ///建立一个维护最小值的优先队列
    priority_queue<PII, vector<PII>, greater<PII>>heap;
    heap.push({0, 1}); ///起始点放入队列
    while (heap.size()) {
        auto t = heap.top(); ///最小值
        heap.pop();
        long long ver = t.second, dd = t.first;
        if (st[ver]) continue; ///该点更新
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dis[j] > dd + w[i]) {
                dis[j] = dd + w[i];
                heap.push({dis[j], j});
            }
        }
    }
}


int main() {
    cin >> n >> m >> q;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);
        add(v, u, w);
    }
    dijkstra();
    long long res = 0;
    while (q--) {
        int x;
        cin >> x;
        res += dis[x] * 2;
    }
    cout << res << endl;






    return 0;
}