最短路
题目描述
给一张无向图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>
using namespace std;
const int inf = 1e9;
int e[110][110];
int main()
{
int n,m,u,v,w,q,i,j,k;
cin>>n>>m;
for(i=0;i<=110;i++)
{
for(j=0;j<=110;j++)
{
if(i==j) e[i][j]=0;
else e[i][j]=inf;
}
}
for(i=1;i<=m;i++)
{
cin>>u>>v>>w;
if(e[u][v]>w)
e[u][v]=e[v][u]=w;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
cin>>q;
while(q--)
{
cin>>u>>v;
if(e[u][v]!=inf)
cout<<e[u][v]<<endl;
else cout<<"-1"<<endl;
}
return 0;
}
转载于:https://www.cnblogs.com/qing123tian/p/11107560.html
