迪杰斯特拉算法-回家过年

https://blog.csdn.net/DERRANTCM/article/details/51710978

#include<stdio.h>
#include<stdlib.h>
int main(){
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF){
        int edge[31][31]={-1};
        int isReached[31]={0};
        int result[31]={-1};
        for(int i=0;i<31;i++){
            for(int j=0;j<31;j++)
                edge[i][j]=-1;
            result[i]=-1;
            isReached[i]=0;
        }
        for(int i=0;i<m;i++){
            int x,y,value;
            scanf("%d %d %d",&x,&y,&value);
            edge[x][y]=value;
        }
         
        result[0]=0;
        isReached[0]=1;
        for(int i=1;i<=n;i++){
            result[i]=edge[0][i];
        }//至此初始化完成
         
        for(int t=0;t<n-1;t++){//t为了计数，图中共n+1个节点，去掉起点共n个，加入n-1个已经可求的单源最短路径
            int min=500;
            int j;
            for(int i=1;i<n;i++){//每次循环找到当前可到达而未到达节点中最短的
                if(isReached[i]==0&&result[i]!=-1&&result[i]<min){
                    j=i;
                    min=result[i];
                }
            }
            isReached[j]=1;//加入最短节点，然后更新当前所有节点的距离
            for(int k=1;k<=n;k++){
                if(isReached[k]==0&&edge[j][k]!=-1)
                    if(result[k]==-1||edge[j][k]+min<result[k]){
                        result[k]=edge[j][k]+min;
                    }
            }
        }
        printf("%d\n",result[n]);
    }
}