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

#include <limits.h>
#include <stdio.h>
#include <malloc.h>
#define MAX 5000
int main() {
    // 好坑呀，这里一定要MAX
    int n;
    int m;
    scanf("%d", &n);
    scanf("%d", &m);
    int g[MAX + 1][MAX + 1];
    for (int i = 0; i <=MAX; i++) {
        for (int j = 0; j <=MAX + 1; j++) {
            g[i][j] = INT_MAX;
        }
    }
    
    for (int i = 0; i < m; i++) {
        int tmp1;
        int tmp2;
        int tmp3;
        scanf("%d", &tmp1);
        scanf("%d", &tmp2);
        scanf("%d", &tmp3);
        g[tmp1][tmp2] = tmp3;
        g[tmp2][tmp1] = tmp3;
    }

    // for (int i = 0; i < n + 1; i++) {
    //     for (int j = 0; j < n + 1; j++) {
    //         printf("g[%d][%d]=%d ", i, j, g[i][j]);
    //     }
    //     printf("\n");
    // }

    int dist[MAX + 1];
    for (int i = 0; i <=MAX; i++) {
        dist[i] = 50000;
    }
// for(int i = 1;i<=n;i++){
//     printf("%d ",dist[i]);
// }
    int flag[MAX + 1];
    for (int i = 0; i <=MAX; i++) {
        flag[i] = 0;
    }

    for (int i = 1; i <= MAX; i++) {
      dist[i] = g[1][i];
    }
    dist[1] = 0;
    flag[1] = 1;
    for (int i = 2; i <= n; i++) {
        dist[i] = dist[i] < g[1][i] ? dist[i] : g[1][i];
    }

    for (int i = 2; i <= n; i++) {
        int tmp =INT_MAX;
        int t = 1;
        for (int j = 1; j <= MAX; j++) {
            if (flag[j] == 0 && dist[j] < tmp) {
                tmp = dist[j];
                t = j;
            }
        }
    if(t!=1){
            flag[t] = 1;
    }
        for (int j = 1; j <= MAX; j++) {
            if (flag[j] == 0 && g[t][j] != INT_MAX) {
                dist[j] = dist[j] < g[t][j] + dist[t] ? dist[j] : g[t][j] + dist[t];

            }
        }
    }
// for(int i = 1;i<=n;i++){
//     printf("%d ",dist[i]);
// }
if(dist[n]!=INT_MAX){
     printf("%d ",dist[n]);
}else {
    printf("-1" );
}
    return 0;
}