当前位置：首页 > ai >正文

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

ai 2025/5/15 9:23:39

经验总结

在这里插入图片描述

邻接表

节点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 secondusing 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() {//initmemset(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; // 输出该节点到起点的最短距离}
}