|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
|
|
|
const int N = 1010;
|
|
|
const int M = 200010;
|
|
|
int n, m;
|
|
|
int S, T, K;
|
|
|
int h[N], rh[N];
|
|
|
int e[M], w[M], ne[M], idx;
|
|
|
int dist[N];
|
|
|
bool st[N];
|
|
|
int cnt[N];
|
|
|
|
|
|
void add(int h[], int a, int b, int c) {
|
|
|
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
|
|
|
}
|
|
|
|
|
|
// 只有点号和距离时，按距离由小到大排序
|
|
|
struct N1 {
|
|
|
int u, d;
|
|
|
const bool operator<(const N1 &b) const {
|
|
|
return b.d < d; // 谁的距离短谁靠前
|
|
|
}
|
|
|
};
|
|
|
|
|
|
// 当有点号+距离+估值函数时，按估值函数值由小到大排序
|
|
|
struct N2 {
|
|
|
int u, d, f;
|
|
|
const bool operator<(const N2 &b) const {
|
|
|
return b.f < f;
|
|
|
}
|
|
|
};
|
|
|
|
|
|
// 经典的Dijkstra,计算终点到图中其它所有点的最短路径
|
|
|
void dijkstra() {
|
|
|
priority_queue<N1> q;
|
|
|
q.push({T, 0});
|
|
|
|
|
|
memset(dist, 0x3f, sizeof dist);
|
|
|
dist[T] = 0;
|
|
|
|
|
|
while (q.size()) {
|
|
|
N1 t = q.top();
|
|
|
q.pop();
|
|
|
int u = t.u;
|
|
|
if (st[u]) continue;
|
|
|
st[u] = true;
|
|
|
for (int i = rh[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (dist[v] > dist[u] + w[i]) {
|
|
|
dist[v] = dist[u] + w[i];
|
|
|
q.push({v, dist[v]});
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int astar() {
|
|
|
priority_queue<N2> q;
|
|
|
q.push({S, 0, dist[S]}); // 起点入队列
|
|
|
|
|
|
while (q.size()) {
|
|
|
int u = q.top().u;
|
|
|
int d = q.top().d;
|
|
|
q.pop();
|
|
|
cnt[u]++; // u出队一次
|
|
|
if (u == T && cnt[u] == K) return d; // 找到到终点的第K短路
|
|
|
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
|
int v = e[i];
|
|
|
if (dist[v] < INF) // 如果是无效借力点，跳过
|
|
|
q.push({v, d + w[i], d + w[i] + dist[v]}); // 点，距离，估值函数值
|
|
|
}
|
|
|
}
|
|
|
return -1;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
cin >> n >> m;
|
|
|
|
|
|
memset(h, -1, sizeof h);//正向图
|
|
|
memset(rh, -1, sizeof rh);//反向图
|
|
|
|
|
|
while (m--) {
|
|
|
int a, b, c;
|
|
|
cin >> a >> b >> c;
|
|
|
add(h, a, b, c); // 正向建图，常规逻辑
|
|
|
add(rh, b, a, c); // 反向建图，用于获取终点t到图中所有点的最短路径。为估值函数作准备
|
|
|
}
|
|
|
|
|
|
cin >> S >> T >> K;
|
|
|
|
|
|
// ① 如果起点与终点最开始是一样的，那么就需要入队列k+1次,这是一个坑
|
|
|
if (S == T) K++;
|
|
|
|
|
|
// ② 先跑一遍Dijkstra,方便计算出估值函数
|
|
|
dijkstra();
|
|
|
|
|
|
// ③ 利用Dijkstra计算出来的终点到任意点的值，再加上当前走过的距离，等于AStar的估值函数
|
|
|
cout << astar() << endl; // A*算法
|
|
|
return 0;
|
|
|
}
|
