题目描述

给一张无向图G(U, E), 询问任意两点的最短距离。

输入

第一行两个整数n，m表示图中结点数和边的数量, 结点从1到n编号。
接下来m行，每行三个整数u，v，w表示u，v之间有一条距离为w的边。
接下来一行一个整数q，表示询问次数。
接下来q行每行两个整数u，v，表示询问u到v的最短距离， 如果u不能到达v输出-1。
数据范围：n <= 100, m <= 5000, q <= 10000， 0 < w <= 1000。

输出

对应输出q行答案。

样例输入

5 10
1 2 1
2 5 10
1 3 2
1 4 4
1 5 6
2 3 4
2 4 3
3 4 1
3 5 4
4 5 2
5
1 4
3 5
2 3
4 2
5 2

样例输出

3
3
3
3
5

代码

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cstring>
using namespace std;
const int M=1005;
const int inf=0x3f3f;
int n,m;
int map[M][M];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=1000;i++)
    for(int j=1;j<=1000;j++)
    	map[i][j]=inf;
    for(int i=0;i<=1000;i++)
    	map[i][i]=0;
    while(m--)
    {
        int u,v,w;
        cin>>u>>v>>w;
        map[u][v]=min(map[u][v],w);
        map[v][u]=map[u][v];
    }
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++)
    		for(int k=1;k<=n;k++)
    		{
        		map[j][k]=min(map[j][k],map[j][i]+map[i][k]);
    		}
    int y;
	cin>>y;
    while(y--)
    {
    	int q,e;
		cin>>q>>e;
		if(map[q][e]<inf) 
			cout<<map[q][e]<<endl;
 		else cout<<-1<<endl;
    } 
    return 0;
}