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

#include <stdio.h>
#include <stdlib.h>
int main() {
    int u, v, w;
    int i, j;
    int n, m, t;
    scanf("%d%d", &t, &m);
    n = 5000;
    int** arc = (int**)malloc((n+1) * sizeof(int*));
    for (i = 0; i < n+1; i++) {
        arc[i] = (int*)malloc((n+1)* sizeof(int));
    }
    int shortest[n + 1];
    int patharc[n + 1];
    int final[n + 1];
    for (i = 0; i < n + 1; i++) {
        for (j = 0; j < n + 1; j++) {
            arc[i][j] = 10000000;
        }
    }
    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        arc[u][v] = arc[v][u] = w;
    }
    for (i = 0; i < n + 1; i++) {
        shortest[i] = arc[1][i];
        patharc[i] = 0;
        final[i] = 0;
    }
    final[1] = 1;
    int k;
    for (int l = 1; l < n; l++) {
        int min = 10000000;
        for (i = 1; i <= n; i++) {
            if (final[i] != 1 && shortest[i] < min) {
                min = shortest[i];
                k = i;
            }
        }
        final[k] = 1;
        if (k == t) {
            printf("%d", shortest[k]);
            return 0;
        }
        for (j = 1; j <= n; j++) {
            if (final[j] != 1 && shortest[j] > min + arc[k][j]) {
                shortest[j] = min + arc[k][j];
                patharc[j] = k;
            }

        }

    }
    printf("%d", -1);
    for(i=0;i<n+1;i++)
    {
     free(arc[i]);
    }
    free(arc);
    return 0;
}