定制网站开发价格,汕头做网站,北京网站建设成都公司,php网站建设制作给定一个 n个点 m 条边的有向图#xff0c;图中可能存在重边和自环#xff0c; 边权可能为负数。
请你求出从 11 号点到 n 号点的最多经过 k 条边的最短距离#xff0c;如果无法从 1 号点走到 n 号点#xff0c;输出 impossible。
注意#xff1a;图中可能 存在负权回路…给定一个 n个点 m 条边的有向图图中可能存在重边和自环 边权可能为负数。
请你求出从 11 号点到 n 号点的最多经过 k 条边的最短距离如果无法从 1 号点走到 n 号点输出 impossible。
注意图中可能 存在负权回路 。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。
点的编号为 1∼n。
输出格式
输出一个整数表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径则输出 impossible。
数据范围
1≤n,k≤500 1≤m≤10000 1≤x,y≤n 任意边长的绝对值不超过 10000。
输入样例
3 3 1
1 2 1
2 3 1
1 3 3
输出样例
3Bellman - ford 算法是求含负权图的单源最短路径的一种算法效率较低代码难度较小。其原理为连续进行松弛在每次松弛时把每条边都更新一下若在 n-1 次松弛后还能更新则说明图中有负环因此无法得出结果否则就完成。 (通俗的来讲就是假设 1 号点到 n 号点是可达的每一个点同时向指向的方向出发更新相邻的点的最短距离通过循环 n-1 次操作若图中不存在负环则 1 号点一定会到达 n 号点若图中存在负环则在 n-1 次松弛后一定还会更新)
对于含有负权边的问题不能使用dijkstra进行求解
代码演示
#include iostream
#include vector
#include algorithm
#include cstring
using namespace std;const int N 550,M 100010;
int n,m,k;
int dist[N],backup[N];// backup数组是复制上一次dist数组中的值 struct Edge
{int a,b,w;
} edge[M];void bellman_ford()
{memset(dist,0x3f,sizeof dist);dist[1] 0;for(int i0;ik;i){//备份数组的作用是防止串联//串联这个词可能很抽象很多人不理解我们考虑这样一个场景//在一次迭代中 我们分别更新dist[2]dist[3] 2-3,如果我们直接使用dist数组进行更新//那么dist[3]就会用 更新过的dist[2] 来更新dist[3],这里实际上是 dist[1] w(1, 2) w(2, 3)//这意味着我们使用了两条边来更新dist[3],这是不符合要求的所以我们需要备份数组来确保每次迭代只会使用一条边来更新 dist数组//这样每次更新使用的边数就在我们的可控范围之内。//通过使用备份数组我们每次迭代 都会比上一次多使用一条边是逐次增加的最后我们就可以得到最大使用k条边的结果memcpy(backup,dist,sizeof dist);for(int j0;jm;j){int a edge[j].a,b edge[j].b,w edge[j].w;dist[b] min(dist[b],backup[a]w);}}}int main(void)
{// n 是图中的点数m 是总共的边数,k 是限制的路径数 scanf(%d%d%d,n,m,k);for(int i0;im;i){int a,b,w;scanf(%d%d%d,a,b,w);edge[i] {a,b,w};}bellman_ford();// 这里是因为如果存在负权边是则不会有更新操作 if(dist[n] 0x3f3f3f3f/2) puts(impossible);else printf(%d\n,dist[n]);return 0;
}
