第k短路

178. 第K短路 - AcWing题库 给定一张 $N$ 个点（编号 $1,2\dots 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

思路

一个显而易见的解法是用朴素BFS, 第一次枚举到终点时就是第一短路, 第二次就是第二最短路, 经过第k次时就是第k最短路。 再看一下时间复杂度, $1000$个点, $1e4$ 条边, 假设每个点10条边, 即 $10^{1000}$ , 肯定超时。这么大的范围必须通过更优化的方式解决。

BFS的优化有双向BFS和A-star, 双向显然也会超时, $2\times 10^{500}$ 一样结果。 那么只有A-star了, 这次不是只求一次最短路, 故需要把只入队最小权值改为能入队都入队, 不过出队仍然是最小权值出队, 保证是最短路。 而预期函数需要满足小于等于真实值, 很难通过计算得出, 这里直接以终点为起点做一次整个图的dijkstra, 求出每个点的最短路径, 以该值作为预期值。

最后就是在第k次时输出结果即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <queue>
#define x first
#define y second 
using namespace std;
typedef pair<int,int> PII;
typedef pair<int, pair<int,int>> PIII;
const int N = 1e3 + 10, M = 2e4 + 10;
int h[N], hr[N], e[M], w[M], ne[M], idx;
int n,m;
int S,T,K;
int dist[N];
bool st[N];
 
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()
{
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0,T});
    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;
    while(q.size())
    {
        auto t = q.top();
        q.pop();
        int ver = t.y;
        if(st[ver]) continue;
        st[ver] = true;
        
        for(int i = hr[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                if(!st[j])
                    q.push({dist[j],j});
            }
        }
    }
}
 
int astar()
{
    priority_queue<PIII,vector<PIII>, greater<PIII>> q;
    q.push({dist[S], {0, S}});
    int cnt = 0;
    if(dist[S] ==  0x3f3f3f3f) return -1;
    while(q.size())
    {
        auto t = q.top();
        q.pop();
        int ver = t.y.y, distance = t.y.x;
        if(ver == T) cnt++;
        if(cnt >= K) return distance;
        
        for(int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            q.push({dist[j] + distance + w[i], {distance + w[i], j}});
        }
    }
    
    return -1;
}
int main()
{
    memset(h, -1, sizeof h);
    memset(hr, -1, sizeof hr);
    cin >> n >> m;
    while(m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(h, a, b, c);
        add(hr, b, a, c);
    }
    cin >> S >> T >> K;
    if(S == T) K++;
    
    dijkstra();
    
 
    cout << astar() << endl;
    return 0;
}