多源最短路 Floyd 详解

经典多源最短路 Floyd 算法

/*
 * 多源最短路
 * 最短路是图论中最为常见的问题之一。按照源点的个数，可以分为单源最短路和多源最短路。
 * 在前几篇博客中，我们介绍了单源最短路的 Dijkstra 算法, Bellman-ford 算法, Spfa 算法。复杂度分别为 O(MlogM)、O(NM)、O(最坏NM，平均KM)。
 *
 * 多源最短路的算法，当然可以通过多次运行单源最短路解决，而且复杂度很低。不过也有几种多源最短路的算法，如 Floyd 最短路算法。
 * Floyd 最短路:
 *      算法复杂度:
 *          O(N^3)
 *      算法思路:
 *          for (int k = 1; k <= n; k ++ ) {
 *              for (int i = 1; i <= n; i ++ ) {
 *                  for (int j = 1; j <= n; j ++ ) {
 *                      dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1]);
 *                  }
 *              }
 *          }
 *      算法证明:
 *          dist[u][v][k] 表示 除了 u, v 源点和终点，路径上所经过的点只能为 1, 2, ..., k中的点，在此条件下的最短路径长度。
 *          那么，动态规划的递归公式可以为
 *          dist[u][v][k] = min(dist[u][v][k-1], dist[u][k][k-1] + dist[k][v][k-1]);
 *          表示倘若最短路径上加入了 k 点，那么必有 u->k 和 k->v 这样的路径作为支撑。
 *          从证明的角度可以看出，Floyd 支持负边，任何最短路都不支持负环。
 *      算法巧解:
 *          空间优化初级版:
 *              可以看出 DP 过程中，可以应用滚动数组求解。 空间复杂度 O(N^2)。
 *          空间优化进阶版:
 *              关键点在于 dist[i][k][k]、dist[k][j][k] 在 k 这个循环中，永远不会更新
 *              也就是说 dist[i][k][k] = dist[i][k][k - 1]，dist[k][j][k] = dist[k][j][k - 1]，因为 k 点的加入不会影响。
 *              因为我们完全可以 忽略第三维度！！！
 *              for (int k = 1; k <= n; k ++ )
 *                  for (int i = 1; i <= n; i ++ )
 *                      for (int j = 1; j <= n; j ++ )
 *                          dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1]);
 */
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int N = 210, INF = 0x3f3f3f3f;
int n, m, q;
int dist[N][N];


int main()
{
    scanf("%d%d%d", &n, &m, &q);

    memset(dist, 0x3f, sizeof dist);
    for (int i = 1; i <= n; i ++ ) {
        dist[i][i] = 0;
    }
    int a, b, c;
    while (m -- ) {
        scanf("%d%d%d", &a, &b, &c);
        dist[a][b] = min(dist[a][b], c);
    }

    for (int k = 1; k <= n; k ++ ) {
        for (int i = 1; i <= n; i ++ ) {
            for (int j = 1; j <= n; j ++ ) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    while (q -- ) {
        scanf("%d%d", &a, &b);
        if (dist[a][b] >= INF / 2) {
            printf("impossible\n");
        } else {
            printf("%d\n", dist[a][b]);
        }
    }
    return 0;
}