You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
45 lines
1.2 KiB
45 lines
1.2 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 1e4 + 10;
|
|
const int INF = 0x3f3f3f3f;
|
|
int n, m, T;
|
|
// 邻接表
|
|
int idx, e[N], ne[N], h[N], w[N];
|
|
void add(int a, int b, int c) {
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
}
|
|
|
|
int backup[N]; // 拷贝一下d数组,避免出现串联
|
|
int d[N]; // 最短距离
|
|
|
|
int bellman_ford() {
|
|
memset(d, 0x3f, sizeof d);
|
|
d[1] = 0;
|
|
|
|
while (T--) {
|
|
memcpy(backup, d, sizeof d); // 每次更新前memcpy避免出现串联
|
|
for (int u = 1; u <= n; u++) // 执行n次松驰操作
|
|
for (int i = h[u]; ~i; i = ne[i]) { // 枚举每个出边
|
|
int v = e[i];
|
|
d[v] = min(d[v], backup[u] + w[i]);
|
|
}
|
|
}
|
|
if (d[n] > INF / 2) return INF; // 因为有负权边所以可能出现d[n]比0x3f3f3f3f稍微小一些
|
|
return d[n];
|
|
}
|
|
int main() {
|
|
cin >> n >> m >> T;
|
|
memset(h, -1, sizeof h);
|
|
while (m--) {
|
|
int a, b, c;
|
|
cin >> a >> b >> c;
|
|
add(a, b, c);
|
|
}
|
|
int t = bellman_ford();
|
|
if (t == INF)
|
|
puts("impossible");
|
|
else
|
|
cout << t << endl;
|
|
return 0;
|
|
}
|