dijkstra 算法

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn =10100;

int g[maxn][maxn],n,m;
int dis[maxn],status[maxn];


void dij(int start){
    memset(status,0,sizeof(status));
    memset(dis,0x3f,sizeof(dis));
    dis[start]=0;
    status[start] = 1;
    for(int ti=1;ti<=n;++ti){
        int pick=-1;
        for(int i=1;i<=n;++i){
            if(status[i] == 1){
                if(pick== -1|| dis[i]< dis[pick])
                pick=i;
            }
        }
        if(pick== -1){
        break;
        }
        status[pick] = 2;
        for(int i=1;i<=n;++i){
            if(status[i] ==0|| status[i] == 1){
                if(g[pick][i] != -1){
                    status[i] = 1;
                    dis[i]=min(dis[i],dis[pick]+g[pick][i]);
                } 
            }
        }
    }
}



int main(){
    memset(g,-1,sizeof(g));

    cin>>n>>m>>s;
    for(int i=1;i<=m;++i){
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=g[y][x]=z;
    }
    dij(s);
    for(int i=1;i<=n;++i)
    {
        if(dis[i]== -1 )
        cout<<2147483647<<" ";
        else
        cout<<dis[i]<<" ";
    }
}