题目描述

有边数限制的最短路

给定一个 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
难度：简单
时/空限制：1s / 64MB

题解

本题考察的是bellman-ford算法，由于题目中说明有负权边，所以必须用bellman算法，并且有边数限制，可以理解为假设我们今天需要从a - >b，其中需要转线k轮，频繁的转线会让我们的体验变差，所以当我们规定一个k，不超过k的前提下，到达b点的最短路径。

• bellman是通过更新n轮所有边， 让所有的点进行n次更新，最终得到结果。
• 注意，当有负权回路的情况下，若 a - > b -> c, a-> d ->a， 如果a -> d无法从d点到c实际上不会影响a -> c点的计算。
• 并且由于会出现负权，我们规定的0x3f3f3f3f为最大值实际上不能作为计算，因为当该点为0x3f3f3f3f我们也会更新其他点，其他点可能是0x3f3f3f3f - x的值，由于题目说有500个点，每条边最多为10000，则该点可能更新为0x3f3f3f3f - 500 * 10000 =3F 3EF2 F3FF;所以最后判断的时候if(res < 0x3f3f3f3f /2)即可。

#include<iostream>
using namespace std;

#include<cstring>

const int N = 510;
const int M = 10010;
int n,m,k;
struct edge{
    int a,b,w;//入边，出边，权值
}edges[M];
int backup[M];
int dist[M];

int Bellman()
{
    memset(dist,0x3f,sizeof dist);
    dist[0] = 0;
    //更新k个轮次
    for(int i = 0;i < k;++i)
    {
        memcpy(backup,dist,sizeof dist);
        //每次用backup更新，避免串联更新，就不是k次更新了
        for(int j = 0;j < m;++j)
        {
            //每次拿到每一条边，更新出边，backup[a]是从0到a的一个距离，w是从a->b的一个距离，dist[b] = min (backup[a] + w,dist[b]);
            int a = edges[j].a;
            int b = edges[j].b;
            int w = edges[j].w;
            int num = backup[a];
            dist[b] = min(num + w,dist[b]);//更新这个出边的距离
            //cout << a+1 << "->" << b+1 << "->" << dist[b] << endl;
        }
    }
   
    return dist[n- 1];
}
int main()
{
    cin >> n >> m >> k;
    for(int i = 0;i < m;++i)
    {
        int x,y,z;
        cin >> x >> y >> z;
        edges[i] = {x - 1,y - 1 ,z};
    }
    int res = Bellman();
    if(res < 0x3f3f3f3f /2)
    cout << res;
    else
    cout << "impossible";
    
    return 0;
}

end

• 喜欢就收藏
• 认同就点赞
• 支持就关注
• 疑问就评论