C4-E 图查询最小距离

题目描述

给出一个 $n $个点 mm 条边的有向图，共有 qq 次询问，每次询问两个点$ u$ 到 $v $的最小距离，若从点 uu 无法到达点$ v$，则输出 −1。

注意：图中可能有重边，且我们认为任意一点到其自身的距离为 0。

输入

第一行两个正整数$ n,m (1≤n≤300,1≤m≤\frac {n(n−1)}2)$，分别表示图中点的数量和边的数量。

接下来$ m$ 行，每行三个正整数 u,v,w(1≤u,v≤n,1≤w≤109)u,v,w (1≤u,v≤n,1≤w≤10^9)，表示从点$ u $到点 vv 有一条距离为$ w $的有向边。

第$ m+2$ 行一个正整数 $q (1≤q≤10^5) $表示询问的次数。

接下来 qq 行，每行两个正整数$ u,v (1≤u,v≤n)，表示询问从点，表示询问从点 u $到点 $v $的最小距离。

输出

对于每组询问，输出一个整数表示点$ u$ 与点 $v $之间的最小距离。

输入样例

1
2
3
4
5
6
7
8
9
10
3 4
1 2 4
1 3 2
3 2 1
1 2 7
4
1 2
2 1
3 2
3 3

输出样例

1
2
3
4
3
-1
1
0

题目分析

此题nn的范围比较小可以考虑使用邻接矩阵，使用Floyd−WarshallFloyd-Warshall算法时间复杂度为O(n3)O(n^3)。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>
using namespace std;
void Floyd(vector<vector<long long>> &graph)
{
    int n = graph.size() - 1;
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (graph[i][j] > graph[i][k] + graph[k][j])
                {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> graph(n + 1, vector<long long>(n + 1, 1e12));
    for (int i = 1; i <= n; i++)
    {
        graph[i][i] = 0;
    }
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        if (w < graph[u][v])
        {
            graph[u][v] = w;
        }
    }

    Floyd(graph);

    int q;
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        if (graph[u][v] == 1e12)
        {
            cout << "-1\n";
        }
        else
        {
            cout << graph[u][v] << endl;
        }
    }

    return 0;
}