迪杰斯特拉算法+邻接举证解决单源最短路径问题

#include <climits>
#include <cstdio>
#include <iostream>
using namespace std;
#define  maxs 5001
int main() {
    // 定义 顶点数 边数 邻接矩阵
    int n,m,a[maxs][maxs];
    for(int i=0;i<maxs;i++){
        for(int j=0;j<maxs;j++){
            a[i][j]=INT_MAX;
        }
    }
    // 输入数据 按照格式来
    scanf("%d %d\n",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d %d %d\n",&x,&y,&z);
        // 无向图对称性
        a[x][y]=z;
        a[y][x]=z;
    }
    // 初始化处理好，定义 距离  访问标志  最小代价
    int dist[maxs],visit[maxs],cur=1;
    for(int i=0;i<maxs;i++){
       dist[i]=INT_MAX;
       visit[i]=0;  
    }
    visit[cur]=1;
    for(int i=2;i<maxs;i++){
       if(a[cur][i]!=INT_MAX) dist[i]=a[cur][i];  
    }
    for(int k=1;k<maxs;k++){
       int min=0;
       for(int i=2;i<maxs;i++){
          if(visit[i]==0&&dist[i]<dist[min]) min=i;
       }
       cur=min;
       visit[cur]=1;
       if(min==n) {
         printf("%d",dist[n]);
         return 0;
       }
       // 更新距离的满足条件 与prim算法区别所在
       for(int i=2;i<maxs;i++){
          // 未被访问过 且 距离和 比当前的小
          if(visit[i]==0&&(a[cur][i]<INT_MAX)&&((dist[cur]+a[cur][i])<dist[i]))dist[i]=dist[cur]+a[cur][i];
       }
    }
    printf("-1");
    return 0;
}
// 64 位输出请用 printf("%lld")