1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int inf = 0x7f7f7f7f;
inline int __read()
{
int x(0), t(1);
char o (getchar());
while (o < '0' || o > '9') {
if (o == '-') t = -1;
o = getchar();
}
for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
return x * t;
}
int n, p, k, cur;
int head[maxn], edge[maxn], __prev[maxn], cost[maxn];
inline void _addedge(int u, int v, int w)
{
__prev[++cur] = head[u];
head[u] = cur;
edge[cur] = v;
cost[cur] = w;
}
inline void __addedge(int u, int v, int w)
{
_addedge(u, v, w), _addedge(v, u, w);
}
int dis[maxn];
bool vis[maxn];
inline void SPFA()
{
memset (dis, 0x7f, sizeof dis);
deque <int> Q;
Q.push_back(1);
dis[1] = 0;
while (!Q.empty()) {
int now = Q.front();
Q.pop_front();
vis[now] = 0;
for (int i = head[now]; i; i = __prev[i]) {
const int v = edge[i];
if (dis[v] <= max(dis[now], cost[i])) continue;
dis[v] = max(dis[now], cost[i]);
if (vis[v]) continue;
if (Q.empty() || dis[v] <= dis[Q.front()]) Q.push_front(v);
else Q.push_back(v);
vis[v] = 1;
}
}
if (dis[n * (k + 1)] == inf) puts("-1");
else printf ("%d\n", dis[n * (k + 1)]);
}
int main()
{
n = __read(), p = __read(), k = __read();
while (p--) {
int u = __read(), v = __read(), a = __read();
__addedge(u, v, a);
for (int i = 1; i <= k; ++i) {
__addedge(i * n + u, i * n + v, a);
_addedge((i - 1) * n + u, i * n + v, 0);
_addedge((i - 1) * n + v, i * n + u, 0);
}
}
SPFA();
system("pause");
}
|