Dijkstra算法
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18+10;
vector< pair<ll,ll> > G[100000+10];
ll n,m,s,d[100000+10];
bool vis[100000+10];
void dijkstra(){
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > que;
for(ll i=1;i<=n;i++)d[i]=inf;
d[s]=0;
que.push(make_pair(0,s));
while(que.empty()==false){
ll u=que.top().second;que.pop();
if(vis[u])continue;
vis[u]=true;
for(ll i=0;i<G[u].size();i++){
ll v=G[u][i].first,w=G[u][i].second;
if(d[v]>d[u]+w){
d[v]=d[u]+w;
que.push(make_pair(d[v],v));
}
}
}
}
int main(){
cin >> n >> m >> s;
for(ll i=1;i<=m;i++){
ll u,v,w;
cin >> u >> v >> w;
G[u].push_back(make_pair(v,w));
}
dijkstra();
for(ll i=1;i<=n;i++){
cout << d[i] << ' ';
}
return 0;
}