最短距离查询算法：C++ 代码实现与优化

问题描述

给定一个包含 n 个顶点和 m 条边的有向图，图中不存在重边和自环，边的权重都是整数。再给定 k 次查询，每次查询包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短路径的距离。如果路径不存在，则输出 'impossible'，如果存在，则输出最短路径的距离。

输入格式

第一行包含三个整数 n, m, k。

接下来 m 行每行包含三个整数 x, y, z，表示存在一条从点 x 到点 y 的有向边，边的权重为 z。

接下来 k 行，每行对应依次询问，包含两个整数 a, b，表示询问从顶点 a 到顶点 b 的最短路径距离。

输出格式

共 k 行，每行输出一个整数，表示这次询问的结果，如果两点间存在最短路径，则输出最短路径的距离，如果不存在，则输出 'impossible'。

示例

样例输入 #1

样例输出 #1

impossible
impossible
impossible
impossible
impossible
impossible
8
impossible

代码实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e8;

int n, m, k;
int dist[N][N];

int main()
{
    cin >> n >> m >> k;

    memset(dist, 0x3f, sizeof dist);
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> 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 (k -- )
    {
        int a, b;
        cin >> a >> b;
        if (dist[a][b] > INF / 2) puts("impossible");
        else cout << dist[a][b] << endl;
    }

    return 0;
}

代码分析

代码首先使用 memset 函数将 dist 数组初始化为一个很大的值，表示两点之间不存在路径。
然后，代码使用循环遍历所有边，并将边的权重赋值给 dist 数组。
接着，代码使用 Floyd-Warshall 算法计算所有点对之间的最短路径距离。
最后，代码使用循环遍历所有查询，并根据 dist 数组输出查询结果。

优化

代码中使用 INF / 2 作为判断路径是否存在的一个阈值，避免了使用 INFINITY 导致溢出的问题。
代码中使用 min 函数来更新 dist 数组，避免了使用 if 语句，提高了代码效率。

应用场景

最短距离查询算法在很多领域都有应用，例如：

路径规划：例如导航软件，可以利用最短距离查询算法来计算最优路线。
网络路由：例如网络设备，可以利用最短距离查询算法来计算数据包的最佳传输路径。
物流配送：例如物流公司，可以利用最短距离查询算法来规划配送路线，提高配送效率。

总结

最短距离查询算法是一种常见的图论算法，可以用来解决很多实际问题。本文介绍了使用 Floyd-Warshall 算法解决最短距离查询问题的方法，并提供了 C++ 代码实现和优化。希望本文能够帮助读者更好地理解和应用最短距离查询算法。