题目链接

算法：BellmanFord算法 $O(n*m)$

存在负权边时使用 特别适合本题这种问不超过k条边的最短路径的情景
讲一下算法流程
首先将图以结构体数组形式存储 BellmanFord算法特别自由 怎么存都可以

struct Edge{
    int a,b,c;//ab为起点 终点 c为权重
}edge[10010];

然后调用bellmanford函数，在函数中 先将存储最短路径的dist数组初始化为正无穷(0x3f3f3f3f)
接下来开始一个二重循环 外面的大循环循环k次 因为题目要求不超过k条边的最短路径
大循环内部 last数组备份dist数组防止发生串联（即用已经更新过的dist[a]来更新dist[b]，详见代码注释）
然后就是与dijkstra算法类似的松弛操作

for (int i=0;i<k;i++){
        memcpy(last,dist,sizeof dist);
        for (int j=0;j<m;j++){
            auto e=edge[j];
            dist[e.b]=min(dist[e.b],last[e.a]+e.c);
        }
    }

最后我们对d[n]进行判定 若大于0x3f3f3f3f/2则说明不存在最短路径
小于则输出结果
ps：根据题目数据范围 应该大于5*1e6就可以了等y总解答

C++ 代码

#include <iostream>
#include <cstring>
using namespace std;
int n,m,k;
int dist[890],last[890];
struct Edge{
    int a,b,c;
}edge[10010];
//bellman_ford相当自由 用结构体邻接表都可以存
void bellman_ford(){
    memset(dist,0x3f,sizeof dist);
//先将存储最短路径的dist数组初始化为正无穷(0x3f3f3f3f)
    dist[1]=0;
    for (int i=0;i<k;i++){
        memcpy(last,dist,sizeof dist);
//last数组备份dist数组防止发生串联
//所谓串联就是用已经更新过的dist[a]来更新dist[b]
//每一轮循环得到的dist数组都是不超过i条边的最短路径
//根据我们的松弛操作 dist[e.b]=min(dist[e.b],last[e.a]+e.c);
//若让更新过的dist[a]去更新dist[b]
//就相当于用可能已经走过了i条边的路径1->a更新dist[b]
//得到可能已经走过了i+1条边的路径1->b
//这应该是下一轮应该进行的操作 如果有下一轮的话
        for (int j=0;j<m;j++){
            auto e=edge[j];
            dist[e.b]=min(dist[e.b],last[e.a]+e.c);
        }
    }
}
int main (){
    cin>>n>>m>>k;
    for (int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        edge[i]={a,b,c};
    }
    bellman_ford();
    if (dist[n]>5*1e6) cout<<"impossible";
    //if(dist[n]>0x3f3f3f3f/2) cout<<"impossible";
    else cout<<dist[n]<<endl;
// 最后我们对d[n]进行判定 若大于0x3f3f3f3f/2则说明不存在最短路径
// 小于则输出结果
// ps：根据题目数据范围 应该大于5*1e6就可以了等y总解答 
    return 0;
}