单源最短路dijkstra
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
priority_queue<pair<int,int> >qwq;
int n,m,s,t;
int dis[maxn],head[maxn];
bool vis[maxn];
struct node
{
int to;
int next;
int dis;
}e[maxn*2];
inline void add(int u,int v,int w)
{
++t;
e[t].to = v;
e[t].next = head[u];
e[t].dis = w;
head[u] = t;
}
inline void dijkstra(int st)
{
for(int i=1;i<=n;i++) dis[i] = 1000000007;
dis[st] = 0;
qwq.push(make_pair(0,st));
while(!qwq.empty())
{
int p = qwq.top().second;
qwq.pop();
if(vis[p]) continue;
vis[p] = true;
for(int i=head[p];i>0;i=e[i].next)
{
int v = e[i].to;
int d = e[i].dis;
if(dis[v]>dis[p]+d)
{
dis[v] = dis[p]+d;
qwq.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
cin>>n>>m>>s;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
add(v,u,w);
}
dijkstra(s);
for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
cout<<endl;
return 0;
}
