bellman

admin管理员组

文章数量:1122853

bellman

首先认真读题：（acwing853）

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

请你求出从 1 号点到 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

输出样例：

3

 本题相较于最短路加了边数限制，必须在满足边数允许的条件下，才可以更新到该点的dist距离，同样我们可以遍历每一条边长

首先是对图片中代码的解释：

backup数组是对更新前dist数组的备份。防止发生串联的情况，例如1-2-3这是一条路径，边数限制k=1时，不备份的话我们可能先将dist【2】的数值更新，再用该数值将dist【3】给更新了。

为避免此类情况，我们可以先将dist数组备份。

对于最后范围false 还是true的条件判定，dist【n】大于0x3f3f3f3f /2;这里的除以2是因为，边的权值可能为负，也会将dist[n]给更新，这样dist[n]并不等于0x3f3f3f3f。

对于该数据范围 >0x3f3f3f3f / 2 就可以判断了；

以及要考虑到返回的数据值，如果dist【n】数据已被更新，返回d【n】，未被更新返回-1或者其他值来判断输出情况，要考虑最后d【n】被更新时恰好等于  判断未被更新的返回值的情况。所以这里函数用bool类型较好

本文标签： bellman