题目描述
给定一张 $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 \le S,T \le N \le 1000$,
$0 \le M \le 10^4$,
$1 \le K \le 1000$,
$1 \le L \le 100$
输入样例:
2 2
1 2 5
2 1 4
1 2 2
输出样例:
14
/*
key: 提前计算好到达终点的最小代价 (建反向图)
起点 S, 终点 T, 求第 K 短路
每一种状态需要记录三个属性:
1. 最少需要多远能到达终点
2. 当前在哪个点
3. 已经走了多远
当第 k 次出队时,即为第 k 短路
*/
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1010, M = 20010;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dist[N];
int cnt[N];
bool st[N];
int n, m, a, b, c, S, T, K;
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);
dist[T] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
heap.push({dist[T], T});
while(heap.size())
{
int distance = heap.top().first;
int ver = heap.top().second;
heap.pop();
if(st[ver]) continue;
st[ver] = true;
for(int i = rh[ver];i != -1;i = ne[i])
{
int j = e[i];
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
return ;
}
int Astar()
{
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> heap;
heap.push({dist[S], {S, 0}});
while(heap.size()) // 在求第 K 短路时,每个点最多入队 K 次
{
int all_distance = heap.top().first;
int ver = heap.top().second.first;
int distance = heap.top().second.second;
heap.pop();
cnt[ver] ++;
if(cnt[ver] == K) return all_distance;
for(int i = h[ver];i != -1;i = ne[i])
{
int j = e[i];
if(cnt[j] < K) heap.push({distance + w[i] + dist[j], {j, distance + w[i]}});
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
memset(h, -1, sizeof h), memset(rh, -1, sizeof rh);
while(m --)
{
cin >> a >> b >> c;
add(h, a, b, c), add(rh, b, a, c);
}
cin >> S >> T >> K;
Dijkstra(); // 求到终点的最小代价
if(S == T) K ++; // 要求路径和不能为 0
int res = Astar();
if(res >= 0x3f3f3f3f) res = -1;
cout << res << endl;
return 0;
}