Pig_py @ 2022-04-29 10:54:00
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define itn int
using namespace std;
int n,m,s;
struct code{
int to,nxt,w;
}e[500005];
int h[200005],cnt=0,dis[100005];
int vis[100005];
void add(int x,int y,int w){
cnt++;
e[cnt].to=y;
e[cnt].nxt=h[x];
h[x]=cnt;
e[cnt].w=w;
}
void dij(int s){
for(int i=1;i<=n;i++){
dis[i]=inf;
vis[i]=0;
}
dis[s]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
pq.push(make_pair(0,s));
while(!pq.empty()){
int x=pq.top().second;
pq.pop();
if(!vis[x]){
vis[x]=1;
for(int i=h[x];i;i=e[i].to ){
if(!vis[e[i].to]&&dis[e[i].to ]>dis[x]+e[i].w ){
dis[e[i].to]=dis[x]+e[i].w;
pq.push(make_pair(dis[e[i].to],e[i].to ));
}
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
dij(s);
for(int i=1;i<=n;i++)printf("%d ",dis[i]);
}
by Pig_py @ 2022-04-29 10:58:05
问题已解决,我是小丑终帖。