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

#include <stdio.h>
#include <limits.h>
#define N 5000
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int vcost[N][N];
    int distance[N];
    int vstate[N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            vcost[i][j] = (i == j) ? 0 : INT_MAX;
        }
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        vcost[u - 1][v - 1] = w;
        vcost[v - 1][u - 1] = w;
    }
    for (int i = 0; i < N; i++) {
        vstate[i] = 0;
        distance[i] = vcost[0][i];
    }
    vstate[0] = 1;

    for (int i = 1; i < N; i++) {
        int min = INT_MAX;
        int k = 0;
        for (int j = 0; j < N; j++) {
            if (vstate[j] == 0 && distance[j] < min) {
                k = j;
                min = distance[j];
            }
        }
        vstate[k] = 1;
        for (int j = 0; j < N; j++) {
            if (vstate[j] == 0 && vcost[k][j] != INT_MAX) {
                if (( distance[k] + vcost[k][j] < distance[j])) {
                    distance[j] = distance[k] + vcost[k][j];
                }

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