AcWing 853. 有边数限制的最短路
原题链接
简单
作者:
尽量不说话
,
2021-02-20 00:26:08
,
所有人可见
,
阅读 353
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1E6 + 10;
int n , m, k;
int dist[N], backup[N];
struct Edge
{
int a, b, w;
}edges[N];
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < k; i++)
{
memcpy(backup, dist, sizeof dist);//保留上一层
for(int j = 0; j < m; j++)
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w);//
}
}
return dist[n];
}
int main()
{
cin >> n >> m >> k;
for(int i = 0; i < m; i++)
{
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b , w};
}
int t = bellman_ford();
if(t > 0x3f3f3f3f / 2)
cout <<"impossible";
else
cout << t;
}