#include <bits/stdc++.h>
constexpr int inf=2147483647;
using namespace std;
int dis[100005],vis[100005],n,m,s;
struct edge{
int v,w;
bool operator<(const edge e2)const{
return w>e2.w;
}
};
vector <edge> e[100005];
void Dijkstra_Optimize(int s){
for (int i=0;i<=n;i++){
dis[i]=inf;
}
dis[s]=0;
priority_queue<edge> pq;
pq.push((edge){s,0});
while(!pq.empty()){
int u=pq.top().v;
pq.pop();
if(vis[u]) continue;
vis[u]=1;
for (auto ed:e[u]){
int v=ed.v,w=ed.w;
if(dis[u]+w<dis[v]) {
dis[v]=dis[u]+w;
pq.push((edge){v,dis[v]});
}
}
}
}
int main(){
cin>>n>>m>>s;
for (int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
}
Dijkstra_Optimize(s);
for (int i=1;i<=n;i++){
cout<<dis[i]<<' ';
}
}
请先 登录 后发表评论。
评论
共 1 条神秘代码显示