题目描述

There are n cities and m roads between them. Your task is to process q queries where you have to determine the length of the shortest route between two given cities.

输入

The first input line has three integers n, m and q: the number of cities, roads, and queries.
Then, there are m lines describing the roads. Each line has three integers a, b and c: there is a road between cities a and b whose length is c. All roads are two-way roads.
Finally, there are q lines describing the queries. Each line has two integers a and b: determine the length of the shortest route between cities a and b.
Constraints
1 ≤ n ≤ 500
1 ≤ m ≤ n2
1 ≤ q ≤ 105
1 ≤ a,b ≤ n
1 ≤ c ≤ 109

输出

Print the length of the shortest route for each query. If there is no route, print -1 instead.

样例输入

4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

样例输出

5
5
8
-1
3

多源最短路问题，使用Floyd算法，要注意的是可能有重边，需要在输入时判断一下，去两个点之间最短的边

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=510;
ll d[N][N];
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,m,q;cin>>n>>m>>q;memset(d,0x3f,sizeof(d));for(int i=1;i<=n;i++)d[i][i]=0;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;d[a][b]=min(d[a][b],(ll)c);d[b][a]=min(d[b][a],(ll)c);}for (int k=1;k<=n;k++){for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}while(q--){int a,b;cin>>a>>b;if (d[a][b]==0x3f3f3f3f3f3f3f3f)cout<<"-1\n";elsecout<<d[a][b]<<"\n";}
}