AcWing 853 有边数限制的最短路
发布日期:2021-05-28 16:26:37 浏览次数:10 分类:技术文章

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

题目描述:

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

请你求出从1号点到n号点的最多经过k条边的最短距离,如果无法从1号点走到n号点,输出impossible。

注意:图中可能 存在负权回路

输入格式

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

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

输出格式

输出一个整数,表示从1号点到n号点的最多经过k条边的最短距离。

如果不存在满足条件的路径,则输出“impossible”。

数据范围

1≤n,k≤500,

1≤m≤10000,
任意边长的绝对值不超过10000。

输入样例:

3 3 11 2 12 3 11 3 3

输出样例:

3

分析:

图中存在负权边,且有边数限制,用Bellman-Ford算法,时间复杂度为O(mn)。

Bellman_Ford算法的具体思路就是逐个松弛途中所有的边,最多松弛n-1次即可求出1到n点的最短路径。

以上图为例:初始所有点的距离设为INF,d[A]=0,然后遍历每条边执行松弛操作,d[B]=1,d[C]=5,其它点的距离未松弛成功;继续第二轮,成功执行松弛的有d[D]=3,d[E]=2;第三轮:d[c]=4,d[G]=4,d[F]=5,后面几轮未能松弛,故最短路径d[F] = 5。本题要求最短路径不超过k条边,所以这里每轮的松弛操作不能发生串联操作。按照之前的描述可以看出,第一次松弛仅仅更新了离A相距一条边以内的点的距离,第二轮只会更新离A不超过两条边的点的距离,所以第k轮只会更新离A不超过k条边距离的点,倘若此时d[F]依旧为INF,说明无法在k条边以内到达终点。本题是对最短路径加上了k条边限制,所以第一轮松弛操作尽管更新了B、C的距离,但是在更新BD,BE两条边时依旧不能使用刚更新的B的距离,而是要使用d[B] = INF,上一轮的距离,否则第一轮松弛就会更新到层次为2的D点,不能确保每一轮松弛操作仅向外扩展一个层次,这个过程有点类似于BFS操作。当然,倘若没有k条边限制,这种串联现象可以出现,还会提高速度,更快的松弛更多的边。为什么该算法能够处理负权边,因为dijkstra每个被加入点集的点的最短距离都已经确定了,如果有负权边还会回过头来更新点集的点,引起错误,而Bellman-Ford算法没有这个设定,每轮松弛操作会尝试松弛所有点的距离,不到最后一轮,每个点的距离都有可能变得更小。

#include 
#include
#include
using namespace std;const int maxn = 10005;int d[505],b[505];struct Node{ int x,y,w;}edge[maxn];int n,m,k;int bellman_ford(){ memset(d,0x3f,sizeof d); d[1] = 0; for(int i = 0;i < k;i++){ memcpy(b,d,sizeof b);//备份,防止串联,没有k条边限制可去掉 for(int j = 0;j < m;j++){ auto e = edge[j]; d[e.y] = min(d[e.y],b[e.x] + e.w);//松弛 } } if(d[n] > 0x3f3f3f3f / 2) return -1;//防止负权边更新无穷大 return d[n];}int main(){ scanf("%d%d%d",&n,&m,&k); int x,y,w; for(int i = 0;i < m;i++){ scanf("%d%d%d",&x,&y,&w); edge[i] = {x,y,w}; } if(bellman_ford() == -1) cout<<"impossible"<

 

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

上一篇:AcWing 851 spfa求最短路
下一篇:AcWing 850 Dijkstra求最短路 II

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年02月14日 10时37分14秒