最短距离查询算法 - C++ 代码实现

最短距离查询算法 - 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

6 3 8
3 5 8
3 4 24
4 3 22
6 2
5 3
4 2
1 6
5 3
5 2
3 5
2 4

样例输出 #1

impossible
impossible
impossible
impossible
impossible
impossible
8
impossible

提示

$$1 \le n \le 200$$ $$1 \le k \le n^2$$ $$1 \le m \le 20000$$ 图中的每条边的权重值不大于 50。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

vector<vector<pair<int, int>>> graph;
vector<int> dist;

void dijkstra(int start) {
    dist.assign(graph.size(), INF);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    graph.assign(n + 1, vector<pair<int, int>>());
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        graph[x].push_back({y, z});
    }
    for (int i = 0; i < k; ++i) {
        int a, b;
        cin >> a >> b;
        dijkstra(a);
        if (dist[b] == INF) {
            cout << "impossible" << endl;
        } else {
            cout << dist[b] << endl;
        }
    }
    return 0;
}

解释

这段代码使用 Dijkstra 算法来计算图中两点之间的最短路径距离。

1. 数据结构: graph 是一个邻接表，用于存储图的边信息。dist 数组用于记录起点到各个点的最短距离。
2. Dijkstra 算法: 该算法使用优先队列来维护当前最短距离的点，并不断更新 dist 数组，直到所有点都被访问过。
3. 查询: 对于每个查询，先使用 Dijkstra 算法计算起点到所有点的最短距离，然后输出终点的最短距离。

总结

本篇文章详细介绍了如何使用 C++ 代码解决最短距离查询问题。代码使用了 Dijkstra 算法来计算最短路径距离，并提供了详细的解释和注释。希望这篇文章可以帮助您理解和应用最短路径算法。