脚本宝典收集整理的这篇文章主要介绍了bellman_ford（限制边数的最短路），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

853. 有边数限制的最短路

给定一个 (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 1
1 2 1
2 3 1
1 3 3

输出样例：

3

• @R_424_1304@：(O(nm))

代码

#include<bITs/stdc++.h>
using namespace std;
int n,k,m;
struct Edge
{
    int l,r,w;
}edges[10005];
int d[505],backup[505];
void bellman_ford()
{
    memset(d,0x3f,sizeof d);
    d[1]=0;
    for(int i=0;i<k;i++)
    {
        memcpy(backup,d,sizeof d);
        for(int i=1;i<=m;i++)
        {
            auto [l,r,w]=edges[i];
            d[r]=min(d[r],backup[l]+w);
        }
    }
}
int main()
{
    scanf("%d%d%d",&amp;n,&;m,&k);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&edges[i].l,&edges[i].r,&edges[i].w);
    bellman_ford();
    if(d[n]>0x3f3f3f3f/2)puts("impossible");
    else
        PRintf("%d",d[n]);
    return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的bellman_ford（限制边数的最短路）全部内容，希望文章能够帮你解决bellman_ford（限制边数的最短路）所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。