178. 第K短路（A*启发式算法）

?178. 第K短路 - AcWing题库

给定一张?N?个点（编号?1,2…N），M?条边的有向图，求从起点?S?到终点?T?的第?K 短路的长度，路径允许重复经过点或边。

注意：?每条最短路中至少要包含一条边。

输入格式

第一行包含两个整数?N?和?M。

接下来?M?行，每行包含三个整数?A,B 和?L，表示点?A?与点?B?之间存在有向边，且边长为?L。

最后一行包含三个整数?S,T 和?K，分别表示起点?S，终点?T?和第?K?短路。

输出格式

输出占一行，包含一个整数，表示第?K?短路的长度，如果第?K?短路不存在，则输出 ?1。

数据范围

1≤S,T≤N≤1000
0≤M≤104
1≤K≤1000
1≤L≤100

输入样例：

2 2
1 2 5
2 1 4
1 2 2

输出样例：

14

A * 算法定义了一个对当前状态?x 的估价函数?f(x)=g[x]+h[x]，其中 g[x]?为从初始状态到达当前状态的实际代价，h[x] 为从当前状态到达目标状态的最佳路径的估计代价。每次取出??最优的状态f[x]?，扩展其所有子状态，可以用?优先队列?来维护这个值。

在求解 k?短路问题时，令 h[x]?为从当前结点到达终点 T?的最短路径长度。可以通过在反向图上对结点 T?跑单源最短路预处理出对每个结点的这个值。

?

A*于一种经典的启发式搜索方法，所谓启发式搜索，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上。

传统的算法中，深度优先搜索(DFS)和广度优先搜索(BFS)在展开子结点时均属于盲目型搜索，也就是说，它不会选择哪个结点在下一次搜索中更优而去跳转到该结点进行下一步的搜索。在运气不好的情形中，均需要试探完整个解集空间, 显然，只能适用于问题规模不大的搜索问题中。而与DFS,BFS不同的是，一个经过仔细设计的启发函数，往往在很快的时间内就可得到一个搜索问题的最优解。

1、标记起点s为open，计算起点的估计代价
2、选择open点集中估计代价最小的点
3、如果选中的点∈目标集合T，即到达目标，标记该点closed，算法结束
4、否则，还未到达目标，标记该点closed，对其周围直达的点计算估计代价，如果周围直达的点未标记为closed，将其标记为open；如果已经标记为closed的，如果重新计算出的估计代价比它原来的估计代价小，更新估计代价，并将其重新标记open。返回第2步。

————————————————
版权声明：本文为CSDN博主「一叶执念」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/YiYeZhiNian/article/details/132056786

当起点和终点相同时，K中隐含了一条长度为0的没有边的最短路，但这条路是不对的，因为起点和终点至少包含一条边，所以K++，排除掉长度为0的最短路。此外，K使得边不存在时astar不会返回0而是返回-1。?

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
typedef long long LL;

#define f first
#define s second
const int N = 1e3 + 2, M = 2e4 + 3;
int n,m,S,T,K;
int h[N], hr[N], e[M], w[M], ne[M], idx;
int dist[N];
bool vis[N];
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;


void add(int H[], int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = H[a], H[a] = idx++;
}

//估价函数
void Dijkstra() {
	memset(dist, 0x3f, sizeof dist);
	priority_queue<PII, vector<PII>, greater<PII>>q;
	dist[T] = 0;
	q.push({ dist[T],T });
	while (!q.empty()) {
		PII t = q.top();

		//cout << t.first<<" "<<t.second << endl;

		q.pop();
		if (vis[t.s])continue;
		vis[t.s] = 1;
		for (int i = hr[t.s]; i != -1; i = ne[i]) {
			int s = e[i], d = w[i];
			if (dist[s] > dist[t.s] + d) {
				dist[s] = dist[t.s] + d;
				q.push({ dist[s], s });
			}
		}
	}
}

int astar() {
	priority_queue<PIII, vector<PIII>, greater<PIII>>q;
	int cnt[N] = { 0 };
	q.push({ dist[S],{0,S} });
	while (!q.empty()) {
		auto t = q.top();
		q.pop();

		cnt[t.second.second]++;

		//cout << t.second.second << " " << cnt[t.second.second] << endl;

		if (cnt[T] == K)return t.second.first;
		int a = t.second.second;
		for (int i = h[a]; i != -1; i = ne[i]) {
			int j = e[i];
			if (cnt[j] < K) {
				q.push({ dist[j] + t.second.first+w[i], {t.second.first + w[i],j}});
			}
		}
	}
	return -1;
}

int main() {
	scanf("%d%d", &n, &m);
	memset(h, -1, sizeof h);
	memset(hr, -1, sizeof hr);
	for (int i = 1,a,b,c; i <= m; i++) {
		scanf("%d%d%d", &a, &b, &c);
		add(h, a, b, c);
		add(hr, b, a, c);
	}
	cin >> S >> T >> K;

	if (S == T)K++;

	Dijkstra();
	/*cout << "KKKKKKKKKKKKKKKKKKKKKKKK" << endl;
	for (int i = 1; i <= n; i++) {
		cout << dist[i] << endl;
	}*/

	printf("%d\n", astar());
	return 0;
}