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
79
| #include <iostream>
#include <cstdio>
#include <queue>
#include <climits>
#define inf INT_MAX
using namespace std;
typedef pair <int, int> PII;
const int N = 2e5 + 10, M = 3e6 + 10;
bool vis[N];
int n, m, k, st, ed, res = inf, d[N];
int idx = -1, hd[N], nxt[M], edg[M], wt[M];
inline int num (int x, int y)
{
return x * (k + 1) + y;
}
void dijkstra_with_heap ()
{
for (int i = num(0, 0); i <= num(n - 1, k); i++)
d[i] = inf;
d[num(st, k)] = 0;
priority_queue <PII, vector<PII>, greater<PII> > q;
q.push(make_pair(0, num(st, k)));
while (!q.empty())
{
PII t = q.top();
q.pop();
if (vis[t.second])
continue;
vis[t.second] = true;
for (int i = hd[t.second]; ~i; i = nxt[i])
if (t.first + wt[i] < d[edg[i]])
{
d[edg[i]] = t.first + wt[i];
q.push(make_pair(d[edg[i]], edg[i]));
}
}
}
void add (int a, int b, int c)
{
nxt[++idx] = hd[a];
hd[a] = idx;
edg[idx] = b;
wt[idx] = c;
}
int main ()
{
cin >> n >> m >> k >> st >> ed;
for (int i = num(0, 0); i <= num(n - 1, k); i++)
hd[i] = -1;
for (int i = 1, a, b, c; i <= m; i++)
{
cin >> a >> b >> c;
for (int j = 0; j <= k; j++)
{
int t = num(a, j),
h = num(b, j);
add(t, h, c);
add(h, t, c);
}
for (int j = 1; j <= k; j++)
{
int t = num(a, j),
h = num(b, j - 1);
add(t, h, 0);
}
for (int j = 1; j <= k; j++)
{
int t = num(b, j),
h = num(a, j - 1);
add(t, h, 0);
}
}
dijkstra_with_heap ();
for (int i = 0; i <= k; i++)
res = min(res, d[num(ed, i)]);
cout << res;
return 0;
}
|