本地能过,洛谷re

P4779 【模板】单源最短路径(标准版)

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 您成功发明了复杂度仅为 O(n + m) 的迪杰斯特拉!


|