zztwudi @ 2024-11-24 16:14:13
我编译器上运行得了但洛谷上显示re,望大神指教
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
int to,from,next,val;
}edge[114514];
int n,m,s;
int dis[114514],head[114514];
bool f[114514];
void build(int i,int from,int to,int val){
edge[i].from=from;
edge[i].to=to;
edge[i].val=val;
edge[i].next=head[from];
head[from]=i;
}
void dj(int x){
f[x]=1;
for(int i=head[x];i;i=edge[i].next){
dis[edge[i].to]=min(dis[edge[i].to],dis[x]+edge[i].val);
}
int minn=20050319000,o=-1;
for(int i=1;i<=n;i++){
if(minn>dis[i]&&!f[i]){
minn=dis[i];
o=i;
}
}
if(o!=-1){
dj(o);
}
}
signed main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n;i++){
dis[i]=20050319000;
}
for(int i=1;i<=m;i++){
int tp1,tp2,tp3;
scanf("%d%d%d",&tp1,&tp2,&tp3);
build(i,tp1,tp2,tp3);
}
dis[s]=0;
f[s]=1;
dj(s);
for(int i=1;i<=n;i++){
printf("%d ",dis[i]);
}
return 0;
}
by Eason20120229 @ 2024-11-24 16:17:04
@zztwudi
您成功发明了复杂度仅为