HDU 6705 - path

发表于 更新于 分类于 阅读次数：

题目链接：HDU 6705

题目要在无源有向带圈图中找第\(k\)短的路径。 比赛的时候我用堆动态维护前\(50000\)大的\(d\)（与Dijkstra中\(d\)意义相同），暴力拓边，以TLE告终。 实际上没有必要对所有的边进行拓展，如下图中\(A\)拓展到了\(B\)，这条边是全局最小的边，接着我们用\(B\)去拓展新边的时候，其实只要考虑与\(B\)邻接的最小的一条边，这个时候\(AB+BC\)被加入堆中，但是有可能\(AB+BC\)不是\(AB\)的下一个状态，因为只要比\(AB\)大一点点就可能是它的下一个状态，所以\(AF\)可能影响\(AB+BC\)的排名，所以也要加入堆中。

所以，综上所述，我们对每个点的出边进行排序，用堆动态维护当前最小的路径，每次BFS拓展的时候只要拓展当前点最小的出边和当前边的下一条边即可。 渐进时间复杂度\(O(T(n+q)\log n)\)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 50000 + 5;
struct Edge {
    int from, to; LL cost;
    friend bool operator < (const Edge &u, const Edge &v) {
        return u.cost < v.cost;
    }
};
int T, n, m, q, qr[MAX_N];
LL ans[MAX_N];
vector <Edge> g[MAX_N];
struct Status {
    int from, to, id;
    LL cost;
    friend bool operator < (const Status &u, const Status &v) {
        return u.cost > v.cost;
    }
};
priority_queue <Status> que;
int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d%d", &n, &m, &q);
        for (int i = 1; i <= n; ++i) g[i].clear();
        int u, v, w;
        for (int i = 1; i <= m; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            g[u].push_back({u, v, w});
        }
        while (!que.empty()) que.pop();
        for (int i = 1; i <= n; ++i) sort(g[i].begin(), g[i].end());
        for (int i = 1; i <= n; ++i) {
            if (g[i].size()) que.push({g[i][0].from, g[i][0].to, 0, g[i][0].cost});
        }
        int maxK = -1;
        for (int i = 1; i <= q; ++i) scanf("%d", qr + i), maxK = max(maxK, qr[i]);
        for (int i = 1; i <= maxK; ++i) {
            Status t = que.top(); que.pop();
            ans[i] = t.cost;
            if (g[t.to].size()) que.push({g[t.to][0].from, g[t.to][0].to, 0, t.cost + g[t.to][0].cost});
            if (t.id + 1 < g[t.from].size())
                que.push({
                    g[t.from][t.id + 1].from,
                    g[t.from][t.id + 1].to,
                    t.id + 1,
                    t.cost - g[t.from][t.id].cost + g[t.from][t.id + 1].cost
                });
        }
        for (int i = 1; i <= q; ++i) printf("%lld\n", ans[qr[i]]);
    }
    return 0;
}