duoaidaoc @ 2022-09-19 20:37:09
#include<bits/stdc++.h>
using namespace std;
const int N = 100000;
//链式前向星
struct zzz {
int to;//指向的节点
int val;//边权
int nex;
}e[N];
int top, head[N];
void add(int x,int y,int z) {
e[++top].to = y;
e[top].val = z;
e[top].nex = head[x];
head[x] = top;
}
//ed of 链式前向星
//vis 数组和 dist 数组
int vis[N];
int dist[N];
//自定义的优先队列,里面存的是dist数组的下标
//小根堆,指dist[i]最小
struct cmp {
bool operator()(int x, int y) {
return dist[x] < dist[y];
}
};
priority_queue<int, vector<int>, cmp> qe;
int main() {
//读入n m s。
int n, m, s;
scanf("%d%d%d", &n, &m, &s);
//依然读数据,因为无向图,所以加两次边
for (int i = 1;i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
//dist 元素设为无穷大
memset(dist, 127, sizeof(dist));
//s节点置为初始节点入队且dist置为0
dist[s] = 0;
qe.push(s);
//队列为空的时候说明都访问完毕
while (!qe.empty()) {
//将队首出队,访问相邻节点
int a = qe.top();
vis[a] = 1;
qe.pop();
for (int i = head[a];i;i = e[i].nex) {
//若没有访问过
if (vis[e[i].to] == 0) {
//更新dist
dist[e[i].to] = min(dist[e[i].to], dist[a] + e[i].val);
//入队
qe.push(e[i].to);
}
}
}
//逐个打印
for (int i = 1;i <= n;i++) {
printf("%d ", dist[i]);
}
return 0;
}
by Usada_Pekora @ 2022-09-19 20:57:59
@duoaidaoc 这个 pair
就是一个内置的类型,默认按照第一关键字(first) 排序,第一关键字相同按照第二关键字(second)排序,所以我把 dist
和 a
都塞到里面就会按照 dist
排序。
by duoaidaoc @ 2022-09-19 21:08:00
@Zyingyzzz 我明白了,我之前的代码没有考虑到入队后dist还有更改的可能。其实应该把dist直接放入优先队列,每次入队时动态更新。 其实我之前自己手写小根堆的时候,维护堆的性质只考虑了入堆元素的影响,没有考虑其他元素的dist也变了...... 总之感谢大佬解惑,Orz
by 孤弦奏愿 @ 2023-02-20 18:02:44
@Usada_Pekora 赞!我就说为什么写的模板有的题能过有的题就wa.