题解 | #小红送外卖#

来去的路程是一样的，所以只需要跑一遍dijk就可以算出来，然后就可以计算答案了，注意是无向图就行。

#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <numeric>
#include <ctime>
#include <string>
#include <bitset>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

const ll N = 5e5 + 5, mod = 1e9 + 7, inf = 2e18;
const double esp = 1e-8;

int n, m, q;

struct Node {
    ll v, w;
};

vector<Node>g[N];
bool vis[N];
ll dis[N];

struct node {
    ll id, vlu;
    bool operator<(const node& u)const {
        return u.vlu < vlu;
    }
};

void dijk(int s) {
    for (int i = 0; i <= n + 3; i++) {
        dis[i] = inf;
    }

    priority_queue<node>pq;

    pq.push({s, dis[s] = 0});

    while (!pq.empty()) {
        node tem = pq.top();
        pq.pop();

        if (vis[tem.id])continue;
        vis[tem.id] = true;

        for (auto [y, w] : g[tem.id]) {
            if (dis[y] > dis[tem.id] + w) {
                pq.push({y, dis[y] = dis[tem.id] + w});
            }
        }

    }
}

void solve() {
    cin >> n >> m >> q;

    while (m--) {
        ll u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u,w});
    }

    dijk(1);
    ll ans=0;
    while(q--){
        int x;
        cin>>x;
        ans+=2*dis[x];
    }
    cout<<ans<<'\n';
    // for(int i=1;i<=n;i++){
    //     cout<<dis[i]<<" \n"[i==n];
    // }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int t = 1;
    //cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}