【模板】单源最短路2

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
int findmin(int visit[],int dist[],int n){
    int i=0,min=INT_MAX,index;
    for (i=0; i<n; i++) {
         if(!visit[i]&&dist[i]<min){
            index=i;
            min=dist[i];
        }
    }
    return index;
}
int dijkstra(int** g,int src,int end,int n){
    int i=0,u,k=1,j;
    int dist[n],visit[n],min=INT_MAX,path[n];
    for (i=0; i<n; i++) {
        visit[i]=0,dist[i]=min;
    }
    dist[src]=0;
    for (i=1; i<n; i++) {
        u=findmin(visit,dist, n);
        visit[u]=1,path[k++]=u;
        for (j=1;j<n; j++) {
           if(!visit[j]&&g[u][j]&&(dist[u]+g[u][j]<dist[j])){
                 dist[j]=dist[u]+g[u][j];
           }
        }
    }
    if (dist[end]==min) {
        printf("-1");
    }
    else {
        printf("%d",dist[end]);
    }
    return 0;
}
int main() {
    int n,m,i,j,k,a,b,c;
    scanf("%d%d",&n,&m);
    k=n+1;
    int **g=(int**)malloc(sizeof(int*)*5001);
    for (i=0; i<5001; i++) {
        g[i]=(int *)malloc(sizeof(int)*5001);
    }
    for(i=0;i<5001;i++){
        for (j=0;j<5001;j++) {
            g[i][j]=0;
             
        }
    }
    for (i=0; i<m; i++) {
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=c;
        g[b][a]=c;
    }
    dijkstra(g, 1, k-1, 5001);
    return 0;
 
}

#include <limits.h>
#include <malloc.h>
#include <stdio.h>

#define MAX 5000

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    //使用二维数组存储边的权值，并且行标表示出发点，列标表示到达点
    int map[MAX+1][MAX+1]={0};
    for (int i = 1; i <= MAX; i++) {
        for (int j = 1; j <= MAX; j++) {
                map[i][j] = INT_MAX;
        }
    }
    int u, v, w;
    for (int i = 0; i < m; i++) { // 注意 while 处理多个 case
        scanf("%d %d %d", &u, &v, &w);
        map[u][v] = w;
        map[v][u] = w;
    }

    //Dijkstra算法
    //初始化
    //S表示集合，为1表示在集合中，为0表示不在集合中
    int dist[MAX+1]={0};
    int S[MAX+1]={0};

    for (int i = 1; i <= MAX; i++) {
        dist[i] = map[1][i];
        S[i]=0;
    }
    S[1] = 1;
    dist[1] = 0;

    for(int i=2;i<=n;i++) {
        int min = INT_MAX, min_p=1;
        //找到最小dist
        for (int j = 1; j <=MAX; j++) {
            if (S[j]==0 && min > dist[j]) {
                min = dist[j];
                min_p = j;
            }
        }

        //将min_p节点纳入S
        if(min_p!=1){
            S[min_p]=1;
        }

        for (int j = 1; j <=MAX; j++) {
            if (S[j] == 0 && map[min_p][j] != INT_MAX) { //未纳入S的点,且i能到达j
                int check = map[min_p][j]+dist[min_p];
                //如果1到j的路径较大，则更新
                if (dist[j] > check) {
                    dist[j] = check;
                }
            }
        }
        
    }

    if(dist[n]!=INT_MAX)
        printf("%d", dist[n]);
    else
        printf("-1");
    return 0;
}