[模板]单源最短路 dijkstra版
作者:
多米尼克領主的致意
,
2024-05-07 18:52:33
,
所有人可见
,
阅读 3
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
#define x first;
#define y second;
typedef pair<int, int>pii;
int h[N], idx;
int n, m, s;
struct edge{
int from, to, w;
int ne;
}E[M];
int dist[N];
bool st[N];
void add(int a, int b, int c)
{
E[idx].to = b;
E[idx].w = c;
E[idx].ne = h[a];
h[a] = idx++;
}
void jks()
{
memset(dist, 0x3f, sizeof dist);
dist[s] = 0;
priority_queue<pii, vector<pii>, greater<pii>>heap;
heap.push({0, s});
while(heap.size())
{
auto t = heap.top();
int no = t.y;
heap.pop();
if(st[no])continue;
st[no] = true;
for(int i = h[no];~i;i = E[i].ne)
{
int j = E[i].to;
if(dist[j] > dist[no] + E[i].w)
{
dist[j] = dist[no] + E[i].w;
heap.push({dist[j], j});
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m >> s;
for(int i = 1;i <= m;i++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
jks();
for(int i = 1;i <= n;i++)cout << dist[i] << " ";
return 0;
}