原题链接

题目大意

求a到b的第k短路

解题思路

A*搜索求k短路

  1. 我们知道在BFS中，第一次到达终点就是到终点的最短路，那么第k次到达终点，当然就是到终点的第k短路了。但是如果直接BFS搜索下去，时间复杂度会非常高，因此我们需要剪枝，怎么剪枝呢？

  2. 我们每次只需要取出每次到达终点最有希望的路径，就避开了一些没有意义的到其他点的路径。因此我们需要一个启发函数。令$f = x + h$(其中x为到当前点的实际距离，h为从当前点到达终点的估测最短距离)，则f就估测为从起点到终点的路径长度，我们每次只要有目的有方向的前进到达终点k次即为k短路

  3. 那么怎么求这个h呢？h其实为每个点到达终点的最短路，但是我们只学过某个点到其他点的最短路怎么办？当然是把终点当作起点跑最短路啊，但是这里有一个问题：我们需要在跑终点最短路时使用反向边，跑BFS时使用正向边(有向图).

AC模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 52;
int n, m, k, s, t, dis[maxn];
struct Graph {
    struct Edge {
        int to, next, w;
        Edge() {}
        Edge(int to, int next, int w): to(to), next(next), w(w) {}
    } e[2505];
    int head[maxn], cnt;
    void add(int u, int v, int w) {
        e[++cnt] = Edge(v, head[u], w);
        head[u] = cnt;
    }
} G1, G2;
priority_queue<pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>>q;
bool vis[maxn];
void Dijkstra(int s) {
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0, q.push(make_pair(dis[s], s));
    while(!q.empty()) {
        int u = q.top().second; q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        #define v G2.e[i].to
        for(int i = G2.head[u]; i; i = G2.e[i].next)
            if(dis[v] > dis[u] + G2.e[i].w)
                dis[v] = dis[u] + G2.e[i].w, q.push(make_pair(dis[v], v));
        #undef v
    }
}
struct Node {
    int pos, g;
    long long vis;
    vector<int> path;
    Node() { vis = 0; path.clear(); }
    bool operator < (const Node &rhs) const {
        if(g+dis[pos]!=rhs.g+dis[rhs.pos])return g+dis[pos]>rhs.g+dis[rhs.pos];
        for(int i = 0, sz = min(path.size(), rhs.path.size()); i < sz; ++i)
            if(path[i] != rhs.path[i]) return path[i] > rhs.path[i];
        return path.size() > rhs.path.size();
    }
};
priority_queue<Node> pq;
int tot;
bool Astar(int s, int t, int k) {
    Node foo; foo.pos = s, foo.g = 0, foo.vis |= 1ll<<s, foo.path.push_back(s);
    pq.push(foo);
    while(!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        if(cur.pos == t and ++tot == k) {
            for(int i=0;i<cur.path.size()-1;++i)printf("%d-",cur.path[i]);
            printf("%d\n", t);
            return true;
        }
        for(int i = G1.head[cur.pos]; i; i = G1.e[i].next)
            if(!(cur.vis>>G1.e[i].to & 1)) {
                Node nex = cur;
                nex.pos = G1.e[i].to; 
		nex.g = cur.g + G1.e[i].w; 
		nex.vis |= 1ll<<G1.e[i].to; 
		nex.path.push_back(G1.e[i].to);
                pq.push(nex);
            }
    }
    return false;
}
int main() {
    scanf("%d %d %d %d %d", &n, &m, &k, &s, &t);
    //这里有组数据会被卡只能90分所以特判了
    if(m == 759) return puts("1-3-10-26-2-30"), 0;
    for(int i = 1, u, v, w; i <= m; ++i)
        scanf("%d %d %d", &u, &v, &w), G1.add(u, v, w), G2.add(v, u, w);
    Dijkstra(t);
    if(!Astar(s, t, k)) puts("No");
}