Luobuyu's Blog

0%

178.第k短路

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 3.4k 阅读时长 ≈ 3 分钟
使用A星进行启发式搜索，注意实现和启发式函数的选择

178. 第K短路

题目描述：

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

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

数据范围：
$ 1\le S, T \le N \le 1000, 0 \le M \le 10^5\\1\le K \le 1000, 1\le L\le100 $

题解：

解法 $ K $ 短路

  • $ A-star $ , 最坏复杂度为 $ O(nk\log{n}) $ ，此时是一个 $ n $ 元环
  • 可持久化可并堆优化

解法 $ A-star $ ：

估价函数 $ f(x) = g(x) + h(x) $ ，其中 $ g(x) $ 为初始状态到当前状态的实际代价， $ h(x) $ 为从当前状态到目标状态的估计代价。每次取出 $ f(x) $ 最小的状态 $ x $ ，扩展其子状态。

在该题目中，令 $ h(x) $ 为从当前结点到达终点 $ e $ 的最短路径长度（可以跑反图最短路，只需要搞一个反图头结点就行，不需要扩展边集）

跑 $ dijkstra $ 得到 $ h(x) $ ，然后跑 $ A-star $ ，把初始点放入，初始点的 $ f(s) = g(s) + h(s) = h(s) $ ，每次取出 $ f(x) $ 最小的状态，枚举到达的点 $ v $ ， $ f(v) = g(v) + h(v) $ ，关键在于求 $ g(v) $ ， $ g(v) = g(u) + w_{uv} = f(u) - h(u) + w_{uv} $

可以使用 $ \text{pair} $ ，然后将第一维放代价，注意放负值，因为 $ priority\_queue $ 默认是大根堆

优化：由于只需要求出从初始结点到目标结点的第 $ k $ 短路，所以已经取出的状态到达一个结点的次数大于 $ k $ 次时，可以不扩展其子状态。因为之前 $ k $ 次已经形成了 $ k $ 条合法路径，当前状态不会影响到最后的答案。

代码：

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <bits/stdc++.h>
#define ll long long
#define lll long long
namespace FAST_IO
{

    inline char nextChar()
    {
        static char buf[1000000], *p1 = buf, *p2 = buf;
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
    }
#define getch getchar
    template <class T>
    inline void read(T &x)
    {
        T flag = 1;
        x = 0;
        char ch = getch();
        while (ch < '0' || ch > '9')
        {
            if (ch == '-')
                flag = -1;
            ch = getch();
        }
        while (ch >= '0' && ch <= '9')
        {
            x = (x << 3) + (x << 1) + (ch ^ 48), ch = getch();
        }
        x *= flag;
    }

    template <class T, class... _T>
    inline void read(T &x, _T &...y)
    {
        return read(x), read(y...);
    }

    inline void print128(lll x)
    {
        if (x < 0)
            putchar('-'), x = -x;
        if (x > 9)
            print128(x / 10);
        putchar(x % 10 + '0');
    }

} // namespace FAST_IO
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 2e5 + 10;
int t, n, m, k;
int s, e;

struct Edge
{
    int u, v, w, next;
} edge[maxm];
int head[maxn], rhead[maxn], cnt = 0;

inline void addEdge(int u, int v, int w)
{
    // 非常方便的存反图
    edge[++cnt] = {u, v, w, head[u]};
    head[u] = cnt;
    edge[++cnt] = {v, u, w, rhead[v]};
    rhead[v] = cnt;
}
int h[maxn];
struct Node
{
    int u;
    int dis;
    bool operator<(const Node &p) const
    {
        return dis < p.dis;
    }
};

bool vis[maxn];
void dijkstra(int s)
{
    priority_queue<Node> q;
    memset(h, 0x3f, sizeof(h));
    memset(vis, false, sizeof(vis));
    h[s] = 0;
    q.push({s, 0});
    while (q.size())
    {
        auto out = q.top();
        q.pop();

        int u = out.u;
        if (vis[u])
            continue;
        vis[u] = true;

        for (int i = rhead[u]; i; i = edge[i].next)
        {
            int v = edge[i].v;
            if (h[v] > h[u] + edge[i].w)
            {
                h[v] = h[u] + edge[i].w;
                q.push({v, -h[v]});
            }
        }
    }
}
// A星 优先级队列里面放 f(x)
int times[maxn];
int astar()
{
    priority_queue<Node> q;
    q.push({s, -h[s]});
    while (q.size())
    {
        auto out = q.top();
        q.pop();
        int u = out.u;
        int gdis = -out.dis - h[u];
        times[u]++;
        if (times[e] == k)
        {
            return gdis;
        }
        for (int i = head[u]; i; i = edge[i].next)
        {
            int v = edge[i].v;
            if (times[v] < k)
            {
                q.push({v, -(gdis + edge[i].w + h[v])});
            }
        }
    }
    return -1;
}

int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    read(n, m);
    for (int i = 1, u, v, w; i <= m; i++)
    {
        read(u, v, w);
        addEdge(u, v, w);
    }
    read(s, e, k);
    if (s == e) // 至少包含一条边
        k++;
    dijkstra(e);
    int ret = astar();
    cout << ret << endl;
    return 0;
}