Floyd算法

关于Floyd算法的优化思路，因为dist[i][j]和dist[j][i]是对称的，在遍历的时候我们可以让k从0开始，i从0到k，j从k到n。
在初始化dist的时候我们首先比较两个地点的大小，然后从小的向大的方向修路。
最后接收st和ed的时候也是比较大小，从小的向大的出发。

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

// 初始化距离矩阵，动态申请内存并初始化值
long long int** init_dist(int n) {
    long long int** dist = (long long**)malloc((n + 1) * sizeof(long long*));
    for (int i = 0; i <= n; i++) {
        dist[i] = (long long int*)malloc((n + 1) * sizeof(long long int));
        for (int j = 0; j <= n; j++) {
            if (i == j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = LLONG_MAX;
            }
        }
    }
    return dist;
}

// 释放二维数组内存
void free_dist(long long int** dist, int n) {
    for (int i = 0; i <= n; i++) {
        free(dist[i]);
    }
    free(dist);
}

// Floyd - Warshall算法
void floyd_warshall(long long int** dist, int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 0; i <= k; i++) {
            for (int j = k; j <= n; j++) {
                if (dist[i][k]!= LLONG_MAX && dist[k][j]!= LLONG_MAX && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

int main() {
    int N, M, Q;
    scanf("%d %d %d", &N, &M, &Q);
    long long int** dist = init_dist(N);
    for (int i = 0; i < M; i++) {
        long long int w;
        int u,v;
        scanf("%d%d%lld", &u, &v, &w);
        if (w < dist[u][v]) {
            dist[u][v] = w;
            dist[v][u] = w;
        }
    }
    floyd_warshall(dist, N);
    for (int i = 0; i < Q; i++) {
        int st, ed;
        scanf("%d%d", &st, &ed);
        if (dist[st][ed] == LLONG_MAX) {
            printf("-1\n");
        } else {
            printf("%lld\n", dist[st][ed]);
        }
    }
    free_dist(dist, N);
    return 0;
}

修改后的代码

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

// 初始化距离矩阵，动态申请内存并初始化值
long long int** init_dist(int n) {
    long long int** dist = (long long**)malloc((n + 1) * sizeof(long long*));
    for (int i = 0; i <= n; i++) {
        dist[i] = (long long int*)malloc((n + 1) * sizeof(long long int));
        for (int j = 0; j <= n; j++) {
            if (i == j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = LLONG_MAX;
            }
        }
    }
    return dist;
}

// 释放二维数组内存
void free_dist(long long int** dist, int n) {
    for (int i = 0; i <= n; i++) {
        free(dist[i]);
    }
    free(dist);
}

// Floyd - Warshall算法
void floyd_warshall(long long int** dist, int n) {
    for (int k = 1; k <= n; k++) {
        for (int i = 0; i <= k; i++) {
            for (int j = k; j <= n; j++) {
                if (dist[i][k]!= LLONG_MAX && dist[k][j]!= LLONG_MAX && dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

int main() {
    int N, M, Q;
    scanf("%d %d %d", &N, &M, &Q);
    long long int** dist = init_dist(N);
    for (int i = 0; i < M; i++) {
        long long int w;
        int u,v;
        scanf("%d%d%lld", &u, &v, &w);
        if (w < dist[u][v]) {
            dist[u][v] = w;
            dist[v][u] = w;
        }
    }
    floyd_warshall(dist, N);
    for (int i = 0; i < Q; i++) {
        int st, ed;
        scanf("%d%d", &st, &ed);
        if (dist[st][ed] == LLONG_MAX) {
            printf("-1\n");
        } else {
            printf("%lld\n", dist[st][ed]);
        }
    }
    free_dist(dist, N);
    return 0;
}