#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
struct node{
    int num;
    int w;
};
vector<node>gv[10005];
int n,m,s;
int dj[10005];
bool inque[10005];
int main(){
    for(int i = 0;i <10005;i++){
        dj[i]=-1;
        inque[i]=true;
    }
    cin>>n>>m>>s;
    for(int i = 0;i < m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        node temp;
        temp.num=b;
        temp.w=c;
        gv[a].push_back(temp);
    }
    dj[s]=0;
    int s = 1;
    for(int i = 0;i < n;i++){
        int mi=s;
        for(int j = 1;j <= n;j++){
            if(dj[j]<dj[mi]&&inque[j]&&dj[j]!=-1){
                mi=j;
            }
        }
        inque[mi]=false;
        int a=1;
        for(int j = 0;j < gv[mi].size();j++){
            if(dj[mi]+gv[mi][j].w<dj[gv[mi][j].num]||dj[gv[mi][j].num]==-1){
                dj[gv[mi][j].num]=dj[mi]+gv[mi][j].w;   
                if(dj[gv[mi][j].num]>dj[a]){
                    a=gv[mi][j].num;
                }
            }
        }
        s=a;
    }
    for(int i = 1;i <= n;i++){
        if(dj[i]==-1)
            cout<<2147483647<<" ";
        else
            cout<<dj[i]<<" ";
    }
    return 0;
}

洛谷3371

我用的是Dijkstra算法（图论）

哪里错了？？

@xushuoxin @昊然 @乙鸟 @zuotingting