题解 | #【模板】单源最短路2#

#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;
}