题意

小红在第三新北林市的学园城送外卖，学园城中有非常多的学校，学园城里有一个美食街。小红每次会接一些同一个学校的订单，然后从美食街取餐出发，再骑车将外卖送到学校，最后回到美食街，以此往复。

学园城有 n 个结点， m 条道路，美食街为1号结点，剩下的结点都是学校，保证学园城中所有结点连通。给出小红每次要送外卖的学校，请计算小红最少需要骑行的距离。

思路

考察Dijkstra算法的性质

当Dijkstra算法完成后，源点到所有已访问顶点的距离是最短的。然而，对于未访问的顶点，算法不能保证它们到源点的距离是最短的，因为算法一旦一个顶点被确定为已访问，就不会再考虑它。题目说 保证所有结点都是联通的，所以跑完Dijkstra以后，从1出发到达所有结点的距离都是最短的，累加dis[x]*2就是答案

乘以2是因为来回的距离

注意用long long

Cpp代码

#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;
}