Dino_chx @ 2022-11-14 17:00:57
#include<bitset>
#include<queue>
#include<iostream>
#include<cstring>
#include<cstdio>
#define inf 2147483647
using namespace std;
const int N = 1e6 + 10;
struct Edge {
int to, w, next;
} edge[N];
struct PE {
int to, dis;
bool operator<(const PE &e)const {
return dis < e.dis;
}
};
int cntEdge, head[N], dist[N];
bitset<N> vis;
void insert(int u, int v, int w) {
edge[++cntEdge].to = v;
edge[cntEdge].w = w;
edge[cntEdge].next = head[u];
head[u] = cntEdge;
return;
}
int n, m, starter;
priority_queue<PE> q;
void dijkstra() {
for (int i = 0; i <= n; i++) {
dist[i] = inf;
}
dist[starter] = 0;
q.push((PE){starter, dist[starter]});
while (!q.empty()) {
PE top = q.top();
q.pop();
int x = top.to;
if (vis[x])
continue;
vis[x] = 1;
for (int i = head[x]; i; i = edge[i].next) {
int to = edge[i].to, w = edge[i].w;
if (dist[x] + w < dist[to]) {
dist[to] = dist[x] + w;
if (!vis[to])
q.push((PE) {to, dist[to]});
}
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &starter);
for (int i = 1, u, v, w; i <= m; i++) {
scanf("%d%d%d", &u, &v, &w);
insert(u, v, w);
}
dijkstra();
for (int i = 1; i <= n; i++) {
printf("%d ", dist[i]);
}
return 0;
}
by kiritokazuto @ 2022-11-14 17:03:25
优先队列重载是反着的
struct PE {
int to, dis;
bool operator<(const PE &e)const {
return dis > e.dis;
}
};
by xingke233 @ 2022-11-14 17:03:41
@clancysam
优先队列写错辣
struct PE {
int to, dis;
bool operator<(const PE &e)const {
return dis > e.dis;
}
};
by 8atemak1r @ 2022-11-14 17:04:08
@clancysam 优先队列重载运算符写反了
by Dino_chx @ 2022-11-14 20:19:05
谢谢纠错,蒟蒻知道啦。
此贴结