Let's update the concave corner of the radar map.\(Dijkstra\)The shortest circuit of a single source can be handled, that is, the shortest distance between a specified point and each point can be obtained once. Negative edge rights cannot be handled.
#include <bits/stdc++.h>
using namespace std;
int pre[100010], k; //Save pictures
bool vis[100010];//Have you visited it
int n, m, s; //Input
struct edge {
int to, nxt, len; //The chained front list star
} e[1010100];
struct node {
int pos, dis; //number, distance
bool operator < (const node &cmp) const {
return dis > ;//Reload small root heap
}
} dis[1010100];
priority_queue <node> q;
void add(int u, int v, int l) {
e[++k] = {v, pre[u], l};
pre[u] = k;
}
void dijkstra() {
dis[s].dis = 0;//Don't forget
({s, 0}); //Enter the team from the starting point
while (!()) {
node tmp = ();//Prefer to the point with the smallest distance
();//Don't forget this or it will pass away. You have to pop the number from the beginning, otherwise it is possible to pop the number you just pushed.
If (vis[]) continue; //Put off visited points first
vis[] = 1;
//Start relaxation of this node
for (int i = pre[]; i; i = e[i].nxt) {
//Transfer all neighboring nodes of this node
int to = e[i].to;
if (dis[to].dis > dis[].dis + e[i].len) {
//If the distance from s to the current traversal node is greater than the distance from tmp node to the current traversal node, the distance can be updated
dis[to].dis = dis[].dis + e[i].len;
({to,dis[to].dis});
}
}
}
}
int main() {
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= n; i++) dis[i].dis = 2147483647;//Cancer, if there is no solution, you need to output 2^31-1
for (int i = 1; i <= m; i++) {
int u, v, l;
scanf("%d%d%d", &u, &v, &l);
add(u, v, l); //Directed
}
dijkstra();
for (int i = 1; i <= n; i++) {
printf("%d", dis[i].dis);
}
}