You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

105 lines
2.7 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#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;
}