AcWing 853. 有边数限制的最短路
原题链接
简单
作者:
芝居気
,
2021-12-05 19:22:51
,
所有人可见
,
阅读 123
#include<iostream>
#include<unordered_map>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
const int N = 100005;
bool st[N];
typedef struct node
{
int a, b, w;
}node;
node e[N];
int n, m, k;
int last[N];
int ans[N];
void bellman()
{
memset(ans, 0x3f, sizeof ans);
ans[1] = 0;
for (int i = 0; i < k; i++)
{
memcpy(last, ans, sizeof ans);
for (int j = 0; j < m; j++)
{
int a = e[j].a, b = e[j].b, w = e[j].w;
ans[b] = min(ans[b], last[a] + w);
}
}
}
int main()
{
cin >> n >> m >> k;
for (int i = 0; i < m; i++)
{
cin >> e[i].a >> e[i].b >> e[i].w;
}
bellman();
if (ans[n] > 2e8) cout<<"impossible";
else cout << ans[n];
return 0;
}