acwing 1488. 最短距离 超级源点 最短路 堆优化Dijkstra

经验总结

邻接表

节点1连接到节点2，权重为3。
节点1连接到节点3，权重为5。
节点2连接到节点4，权重为2。
g[1] = {{2, 3}, {3, 5}}
g[2] = {{1, 3}, {4, 2}}
g[3] = {{1, 5}}
g[4] = {{2, 2}}

vector<vector<PII>> g;

题目背景

有 N个村庄，编号1到 N。
村庄之间有 M条无向道路，第 i条道路连接村庄 ai和村庄 bi 长度是ci。
所有村庄都是连通的。
共有 K个村庄有商店，第 j个有商店的村庄编号是 xj。
然后给出 Q个询问，第 k个询问给出一个村庄的编号 yk，问该村庄距离最近的商店有多远？

输入格式

第一行包含两个整数 N,M。
接下来 M行，每行包含三个整数 ai,bi,ci，表示第 i 条道路连接村庄 ai和村庄 bi，长度是 ci。
再一行包含整数 K。
接下来 K行，每行包含一个整数 xj，表示第 j个有商店的村庄编号是 xj 再一行包含整数 Q。
接下来 Q行，每行包含一个整数 yk，表示询问编号为 yk的村庄与其距离最近的商店之间的距离。

输入样例：

7 7
1 2 5
1 4 3
2 3 2
2 5 1
3 6 7
5 6 8
6 7 6
3
7
5
4
7
1
2
3
4
5
6
7

输出格式

对于每个询问，输出该询问的结果。

数据范围

输出样例：

3
1
3
0
0
6
0

代码细节

#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

const int N = 100005; 

typedef pair<int, int> PII; // 定义pair类型，用于存储边的权重和目标节点--按照权重排序
int n, m; // n为节点数，m为边数
int dist[N]; 
bool st[N];
vector<vector<PII>> g; // 存储图的邻接表表示


void dijkstral() {
   //init
    memset(dist, 0x3f, sizeof(dist)); 
    dist[0] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, 0}); 
   
    while (!pq.empty()) {
        auto t = pq.top(); // 取出队首元素，距离起点最小的点
        pq.pop();
        int node = t.y, distance = t.x; // 当前节点及其距离
        
        if (st[node]) continue; 
        st[node] = true; // 标记节点为已访问
        
        for (auto it : g[node]) { // 遍历当前节点的所有邻居节点
            int a = it.x, b = it.y; // 获取邻居节点及边的权重
            if (dist[a] > dist[node] + b) { // 更新最短距离
                dist[a] = dist[node] + b;
                pq.push({dist[a], a}); // 将更新后的节点加入优先队列
            }
        }
    }
}

int main() {
    cin >> n >> m; // 输入节点数和边数
    g.resize(n + 1); 
    
	while (m--) {
        int a, b, c; cin >> a >> b >> c; // 输入每条边的两个端点和权重
        g[a].push_back({b, c});
        g[b].push_back({a, c}); // 无向图存两遍
    }
    
	int k; 
	cin >> k; // 输入附加起点的数量
    
	while (k--) {
        int a; cin >> a; // 输入附加起点
        g[0].push_back({a, 0}); // 将附加起点与虚拟起点0连接，权重为0
    }
    dijkstral(); // 运行Dijkstra算法
    int Q;
    cin >> Q; // 输入查询次数
    while (Q--) {
        int a; cin >> a; // 输入查询节点
        cout << dist[a] << endl; // 输出该节点到起点的最短距离
    }
}