AcWing 854 Floyd求最短路
发布日期:2021-05-28 16:26:40 浏览次数:9 分类:技术文章

本文共 1253 字,大约阅读时间需要 4 分钟。

题目描述:

给定一个n个点m条边的有向图,图中可能存在重边和自环,边权可能为负数。

再给定k个询问,每个询问包含两个整数x和y,表示查询从点x到点y的最短距离,如果路径不存在,则输出“impossible”。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数n,m,k

接下来m行,每行包含三个整数x,y,z,表示点x和点y之间存在一条有向边,边长为z。

接下来k行,每行包含两个整数x,y,表示询问点x到点y的最短距离。

输出格式

共k行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出“impossible”。

数据范围

1≤n≤200,

1≤k≤n^2
1≤m≤20000,
图中涉及边长绝对值均不超过10000。

输入样例:

3 3 21 2 12 3 21 3 12 11 3

输出样例:

impossible1

分析:

多源最短路问题,采用Floyd算法,时间复杂度为O(n^3)。

Floyd算法的思想是动态规划。设d[i][j]表示i点到j点的最短距离,i点到j点中间经过某点k,则状态转移方程为d[i][j] = min(d[i][k] + d[k][j],d[i][j])(1<=k<=n);然后用三重循环实现该状态扩散的过程即可。注意对中间节点k的枚举需要放在循环的最外层,否则会出错。

#include 
#include
#include
using namespace std;const int maxn = 205;int d[maxn][maxn],n,m,k;void floyd(){ 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][k] + d[k][j],d[i][j]);}int main(){ scanf("%d%d%d",&n,&m,&k); int x,y,z; memset(d,0x3f,sizeof d); for(int i = 1;i <= n;i++) d[i][i] = 0; for(int i = 0;i < m;i++){ scanf("%d%d%d",&x,&y,&z); d[x][y] = min(d[x][y],z); } floyd(); while(k--){ scanf("%d%d",&x,&y); if(d[x][y] > 0x3f3f3f3f / 2) puts("impossible"); else printf("%d\n",d[x][y]); } return 0;}

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/101062266 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 858 Prim算法求最小生成树
下一篇:AcWing 852 spfa判断负环

发表评论

最新留言

关注你微信了!
[***.104.42.241]2024年02月11日 07时42分24秒