小红送外卖

核心思想是堆优化的Dijkstra算法，基本上是模板题，但是要熟练的写出来还是有点难度。注意无向图的节点插入是双向的，另外边的数组要开大一点。

#include 
using namespace std;
typedef pair PII;
typedef long long int ll;
const int N = 2e5+10;
int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue, greater> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c; h[a] = idx ++ ;
}
int main() {
    memset(h, -1, sizeof h);
    int m, q;
    cin >> n >> m >> q;
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
    }
    dijkstra();
    ll sum = 0;
    int idx;
    while(q--){
        cin >> idx;
        sum += dist[idx];
    }
    cout << sum * 2 << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

import heapq


def dijkstra(n, adj, start):
    dist = [float("inf")] * (n + 1)  # 初始化距离数组，所有距离设为无穷大
    dist[start] = 0  # 起点到自身的距离为0
    heap = [(0, start)]  # 最小堆，存储 (距离, 节点) 元组
    while heap:
        d, u = heapq.heappop(heap)  # 弹出当前距离起点最近的节点
        # if d > dist[u]:
        #     continue  # 如果弹出的距离大于已知最短距离，跳过
        for v, w in adj[u]:  # 遍历当前节点的所有邻接节点
            if dist[v] > dist[u] + w:  # 如果通过当前节点到达邻接节点的距离更短
                dist[v] = dist[u] + w  # 更新最短距离
                heapq.heappush(heap, (dist[v], v))  # 将新的距离和节点加入堆中
    return dist


n, m, q = map(int, input().split())  # 读取节点数n，边数m，目标学校数q
adj = [[] for _ in range(n + 1)]  # 初始化邻接表
for _ in range(m):
    u, v, w = map(int, input().split())  # 读取每条边的信息
    adj[u].append((v, w))  # 添加边 u -> v，权重为 w
    adj[v].append((u, w))  # 添加边 v -> u，权重为 w（无向图）
targets = list(map(int, input().split()))  # 读取目标学校列表
dist = dijkstra(n, adj, 1)  # 计算从节点1到所有节点的最短路径
total = sum(2 * dist[t] for t in targets)  # 计算所有目标学校的往返距离之和
print(total)  # 输出总骑行距离