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
| #include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PI;
typedef pair<int, PI> PII;
const int maxn = 2e5 + 50;
int n, m, S, T, K, tot = -1, head[maxn], rhead[maxn], f[maxn];
struct node {
int nxt_, v_, w_;
} e[maxn << 1];
void add(int head[], int u, int v, int w) {
e[++tot].v_ = v, e[tot].w_ = w, e[tot].nxt_ = head[u];
head[u] = tot;
}
void dijkstra() {
bool vis[maxn];
memset(vis, 0, sizeof(vis)), memset(f, 0x3f, sizeof(f));
priority_queue<PI, vector<PI>> q;
q.push({0, T});
f[T] = 0;
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int i = rhead[u]; ~i; i = e[i].nxt_) {
int v = e[i].v_, w = e[i].w_;
if (f[u] + w < f[v]) {
f[v] = f[u] + w;
q.push({-f[v], v});
}
}
}
}
int astar() {
if (S == T) ++K;
priority_queue<PII, vector<PII>> q;
int cnt[maxn];
memset(cnt, 0, sizeof(cnt));
q.push({0 + f[S], {0, S}});
while (!q.empty()) {
int u = q.top().second.second, d = q.top().second.first;
q.pop();
++cnt[u];
if (cnt[T] == K) return d;
for (int i = head[u]; ~i; i = e[i].nxt_) {
int v = e[i].v_, w = e[i].w_;
if (cnt[v] >= K) continue;
if (f[v] >= 0x3f3f3f3f) continue;
q.push({-(f[v] + d + w), {d + w, v}});
}
}
return -1;
}
int main() {
cin >> n >> m;
int u, v, w;
memset(head, -1, sizeof(head)), memset(rhead, -1, sizeof(rhead));
for (int i = 1; i <= m; ++i) {
cin >> u >> v >> w;
add(head, u, v, w), add(rhead, v, u, w);
}
cin >> S >> T >> K;
dijkstra();
cout << astar() << endl;
return 0;
}
|