题目描述
给定一张 N N N个点（编号 1 , 2 … N 1,2…N 1,2…N）， M M M条边的有向图，求从起点 S S S到终点 T T T的第 K K K短路的长度，路径允许重复经过点或边。
注意： 每条最短路中至少要包含一条边。
输入格式
第一行包含两个整数 N N N和 M M M。
接下来 M M M行，每行包含三个整数 A A A， B B B 和 L L L，表示点 A A A 与点 B B B之间存在有向边，且边长为 L L L。
最后一行包含三个整数 S S S， T T T 和 K K K，分别表示起点 S S S，终点 T T T和第 K K K短路。
输出格式
输出占一行，包含一个整数，表示第 K K K 短路的长度，如果第 K K K 短路不存在，则输出 − 1 -1 −1。
数据范围
1
≤
S
,
T
≤
N
≤
1000
1≤S,T≤N≤1000
1≤S,T≤N≤1000，
0
≤
M
≤
1
0
4
0≤M≤10^4
0≤M≤104，
1
≤
K
≤
1000
1≤K≤1000
1≤K≤1000，
1
≤
L
≤
100
1≤L≤100
1≤L≤100
输入样例
2 2
1 2 5
2 1 4
1 2 2
输出样例
14
算法思想
对于一个图来说，起点到终点可能存在很多条路径，如果求其中最短路径的长度，可以使用图的最短路算法，例如： Dijkstra \text{Dijkstra} Dijkstra、 SPFA \text{SPFA} SPFA…等等。
但题目要求的是第 K K K短的路径长度，朴素的思想是在搜索状态空间时，将当前节点的所有邻边全部扩展，然后在所有路径中寻找第 K K K短的路径，这样会导致要搜索的状态空间非常庞大。因此，为了提高搜索效率，可以考虑使用 A* \text{A*} A*算法，在启发函数的作用下，只需要搜索较少的状态空间就能找到答案。
A* \text{A*} A*算法的基本思想可以参考博主的另一篇文章：每周一算法：A*（A Star）算法。
启发函数
在 A* \text{A*} A*算法中，需要一个优先队列，优先处理综合优先级较高的节点，对于本题来说，综合优先级 f ( n ) = g ( n ) + h ( n ) f(n)=g(n)+h(n) f(n)=g(n)+h(n)，其中 g ( n ) g(n) g(n)表示起点到节点 n n n的距离，那么启发函数 h ( n ) h(n) h(n)表示 n n n到终点的预计代价，那么如何求 h ( n ) h(n) h(n)呢？
对于 A* \text{A*} A*算法来说，如果 h ( n ) h(n) h(n) 始终小于等于节点 n n n到终点的代价，则 A* \text{A*} A*算法算法保证一定能够找到最短路径，因此不妨将启发函数 h ( n ) h(n) h(n)设置为节点 n n n到终点的最短距离。这样可以通过对终点反向求一次最短路，就可以得到每个节点的预计代价，也就是 h ( n ) h(n) h(n)。
第K短路
在 A* \text{A*} A*算法中，如果终点第 1 1 1次从优先队列里取出，此时可以得到到达终点的最小代价。那么要求第 K K K小代价怎么办？其实只需要记录每个节点出队的次数，当终点第 K K K次从优先队列里取出，此时到达终点的距离就是第 K K K小代价。
算法实现
- 使用 Dijkstra \text{Dijkstra} Dijkstra求终点到每个点的最短距离，也就是预计代价 h [ n ] h[n] h[n]
- 将起点的综合优先级，以及起点到自己的距离和起点编号加入优先队列
- 只要队列不空：
- 从队列中取出一个节点 u u u
- 将其出队次数增加 1 1 1，如果终点的出队次数刚好等于 K K K，则返回第 K K K短路的长度
- 遍历
u
u
u的邻边，对每个相邻节点
v
v
v：
- 如果 v v v的出队次数 < K \lt K <K，则将 v v v的综合优先级、以及起点到 v v v距离和节点编号加入优先队列
代码实现
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1005;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
struct edge
{
int v, w;
};
int n, m, S, T, K;
vector<edge> g[N], rg[N];
int st[N], h[N]; //启发函数，保存每个点到终点的最短距离
int cnt[N]; //求每个点出队的次数
//求终点到其它点的最短距离
void dijkstra()
{
memset(h, 0x3f, sizeof h);
priority_queue<PII, vector<PII>, greater<PII>> heap;
h[T] = 0; heap.push({0, T}); //将终点加入优先队列
while(heap.size())
{
auto t = heap.top(); heap.pop();
int u = t.second;
if(st[u]) continue;
st[u] = 1;
for(auto e : rg[u])
{
int v = e.v, w = e.w;
if(h[v] > h[u] + w)
{
h[v] = h[u] + w;
heap.push({h[v], v});
}
}
}
}
int astar()
{
//优先队列存储{综合优先级, {到起点的距离，点的编号}}
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
heap.push({0 + h[S], {0, S}});
while(heap.size())
{
auto t = heap.top(); heap.pop();
int u = t.second.second, d = t.second.first;
cnt[u] ++;
if(cnt[T] == K) return d; //终点出队K次
for(auto e : g[u])
{
int v = e.v, w = e.w;
//如果v已经出队k次了，且astar()并没有结束, 说明从v出发找不到第k短路，就没必要让v继续入队了
if(cnt[v] < K)
heap.push({d + w + h[v], {d + w, v}});
}
}
return -1;
}
int main()
{
scanf("%d%d", &n, &m, &K);
for(int i = 0; i < m; i ++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back({v, w}), rg[v].push_back({u, w});
}
scanf("%d%d%d", &S, &T, &K);
//当起点和终点重合，由于题目要求每条最短路至少要包含一条边，所以需要让K++，保证不输出0
if(S == T) K ++;
//求每个点到终点的最短距离作为启发函数的值
dijkstra();
printf("%d\n", astar());
}