<-录制视频不容易，点个赞再走呗

题目传送门

视频讲解

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510,M = 10010,INF = 0x3f3f3f3f;
int n,m,k;
int dist[N],backup[N];
struct Edge {
    int a,b,w;
}edge[M];
int bellman_ford () {
    memset (dist,0x3f,sizeof (dist));
    dist[1] = 0;
    for (int i = 1;i <= k;i++) {
        memcpy (backup,dist,sizeof (backup));
        for (int j = 1;j <= m;j++) {
            int a = edge[j].a,b = edge[j].b,w = edge[j].w;
            dist[b] = min (dist[b],backup[a]+w);
        }
    }
    return dist[n];
}
int main () {
    cin >> n >> m >> k;
    for (int i = 1;i <= m;i++) {
        int a,b,w;
        cin >> a >> b >> w;
        edge[i] = {a,b,w};
    }
    int ans = bellman_ford ();
    if (ans > INF/2) puts ("impossible");
    else cout << ans << endl;
    return 0;
}