88 lines
2.3 KiB
C++
88 lines
2.3 KiB
C++
#include <iostream>
|
||
#include <vector>
|
||
#include <queue>
|
||
|
||
using namespace std;
|
||
const int INF = 1e9;
|
||
|
||
// A* 专用的状态结构体
|
||
struct State {
|
||
int f, g, u;
|
||
bool operator>(const State& other) const {
|
||
return f > other.f; // 小顶堆，f 小的优先
|
||
}
|
||
};
|
||
|
||
int main() {
|
||
int n, m;
|
||
cin >> n >> m;
|
||
vector<vector<pair<int, int>>> adj(n + 1);
|
||
vector<vector<pair<int, int>>> adjReverse(n + 1);
|
||
for (int i = 0; i < m; ++i) {
|
||
int a, b, t;
|
||
cin >> a >> b >> t;
|
||
adj[a].push_back({b, t});
|
||
adjReverse[b].push_back({a, t});
|
||
}
|
||
int s, t, k;
|
||
cin >> s >> t >> k;
|
||
|
||
// 1. 反向 Dijkstra 计算 h(n)
|
||
vector<int> h(n + 1, INF);
|
||
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> jda;
|
||
|
||
h[t] = 0;
|
||
jda.push({0, t});
|
||
while (!jda.empty()) {
|
||
auto [d, u] = jda.top(); jda.pop();
|
||
if (d > h[u]) continue;
|
||
for (auto& edge : adjReverse[u]) {
|
||
int v = edge.first, w = edge.second;
|
||
if (h[u] + w < h[v]) {
|
||
h[v] = h[u] + w;
|
||
jda.push({h[v], v});
|
||
}
|
||
}
|
||
}
|
||
|
||
// 如果起点终点不连通，h[s] 依然是 INF
|
||
if (h[s] == INF) {
|
||
cout << -1 << endl;
|
||
return 0;
|
||
}
|
||
|
||
// 2. 正向 A* 找第 K 短路
|
||
if (s == t) k++; // 经典细节：起点终点重合，第一条路径长度为 0，需跳过
|
||
|
||
priority_queue<State, vector<State>, greater<State>> astar;
|
||
astar.push({h[s], 0, s}); // f = g + h = 0 + h[s]
|
||
|
||
vector<int> count(n + 1, 0); // 记录每个点被弹出的次数
|
||
|
||
while (!astar.empty()) {
|
||
State curr = astar.top(); astar.pop();
|
||
int u = curr.u;
|
||
int g = curr.g;
|
||
|
||
count[u]++;
|
||
|
||
// 终点第 K 次出堆，就是答案！
|
||
if (count[t] == k) {
|
||
cout << g << endl;
|
||
return 0;
|
||
}
|
||
|
||
// 如果某个点被弹出次数超过 k，说明再从它出发也找不到前 k 短了，优化剪枝
|
||
if (count[u] > k) continue;
|
||
|
||
for (auto& edge : adj[u]) {
|
||
int v = edge.first, w = edge.second;
|
||
// 压入新状态：g 增加实际边权，f 更新为新 g + h[v]
|
||
astar.push({g + w + h[v], g + w, v});
|
||
}
|
||
}
|
||
|
||
cout << -1 << endl;
|
||
return 0;
|
||
}
|