次数限制的最短路径
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;struct E{int x,y,z;
};int INF = 0x3f3f3f3f;
//最高是3f3f3f3f,x y z 如果x是INF说明没有更新，如果结果是比INF/2大说明有负数
//遍历k次，dist[b]与prev[a]+c比较与更新
int main()
{int n,m,k;cin >> n >> m >> k;vector<E> eg(m);vector<int> dist(n+1,INF);vector<int> prev(n+1,INF);for (int i = 0; i < m; i ++ ){cin >> eg[i].x >> eg[i].y >> eg[i].z;}dist[1] = 0;int flag = 0;int a,b,c;for (int i = 1; i <= k; i ++ ){flag = 0;prev = dist;for(auto o: eg){a = o.x; b = o.y; c = o.z;if(prev[a]!=INF){dist[b] = min(dist[b],prev[a]+c);//跟上次的比不然不确定}}}if(dist[n]>INF/2){cout << "impossible";}else{cout << dist[n];}return 0;
}