求帮助!题目和问题代码都在下面。求求啦!
2024-07-06 16:40:07
发布于:浙江
题目描述
给定一个 n 个顶点 m 个边的有向图,图中不存在重边和自环,边的权重都是整数。 再给定 k 次查询,每次查询包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短路径的距离。 如果路径不存在,则输出 impossible,如果存在,则输出最短路径的距离。
提示
1≤n≤200
1≤k≤n^2
1≤m≤20000
图中的每条边的权重值不大于 50
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行每行包含三个整数 x, y, z,表示存在一条从点 x 到点 y 的有向边,边的权重为 z。
接下来 k 行,每行对应依次询问,包含两个整数 a, b,表示询问从顶点 a 到顶点 b 的最短路径距离。
输出格式
共 k 行,每行输出一个整数,表示这次询问的结果,如果两点间存在最短路径,则输出最短路径的距离,如果不存在,则输出 impossible
样例
样例组输入#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
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int x,y,z;
int from,to;
int mp[2005][2005];
int sum=0;
int main(){
cin>>n>>m;
for(int i=1;i<=1000;i++){
for(int j=1;j<=1000;j++){
mp[i][j]=1e9;
}
}
for(int i=1;i<=m;i++){
cin>>x>>y>>z;
mp[x][y]=z;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mp[i][j]>mp[i][k]+mp[k][j]){
mp[i][j]=mp[i][k]+mp[k][j];
}
}
}
}
for(int i=1;i<=k;i++){
cin>>from>>to;
if(mp[from][to]>=1e9)
cout<<mp[from][to];
else
cout<<"impossible";
cout<<endl;
}
return 0;
}
这里空空如也
有帮助,赞一个