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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#define PII pair<int, int>
#define PIII pair<int, pair<int, int>>
using namespace std;
const int N = 1010, M = 20010;
int h[N], rh[N], e[M], ne[M], w[M], dist[N];
bool st[N];
int n, m, S, K, T, idx;
void add(int h[N], int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra()
{
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, T});
memset(dist, 0x3f, sizeof dist);
dist[T] = 0;
while(!heap.empty())
{
auto t = heap.top();
heap.pop();
int num = t.second, distance = t.first;
if (st[num]) continue;
st[num] = true;
for (int i = rh[num]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
}
int astar()
{
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
heap.push({dist[S], {0, S}});
if (dist[0] == dist[S]) return -1;
int cnt = 0;
while(!heap.empty())
{
auto t = heap.top();
heap.pop();
int n = t.second.second, distance = t.second.first;
if (n == T) cnt++;
if (cnt == K) return distance;
for (int i = h[n]; ~i; i = ne[i])
{
int j = e[i];
heap.push({distance + w[i] + dist[j], {distance + w[i], j}});
}
}
return -1;
}
int main()
{
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
cin >> n >> m;
for (int i = 0; i < m; ++i)
{
int a, b, c;
cin >> a >> b >> c;
add(h, a, b, c);
add(rh, b, a, c);
}
cin >> S >> T >> K;
if (S == T) K++;
dijkstra();
cout << astar();
}
|