RenaMoe's Blog

念念不忘，必有回响

0%

题解 P3953 逛公园

发表于 分类于 ， Valine：

给出 n 点 m 边的有向图，设 1 点到 n 点最短路为 d，求长度小于等于 d+k 的路线方案数。

\(n\le 10^5,m\le 2\times 10^5,k\le50\)，每条边边权为非负整数。

若方案数无穷，输出 -1。

因为 0 环的问题，这题绝大部分题解都假了，详情看这里。

思路

分层图

先预处理以 1 和 n 为起点的单源最短路。

考虑 dp，设 \(f[u][i]\) 表示 1 到 u 路径比原先最短路长度多出 i 的方案数。

对于每条边 \(E_{u\rightarrow v}\)，\(f[v][i+dis_u+val_E-dis_v]\Longleftarrow f[u][i]\)。

可以发现每条边上的转移 \(dis_u+val_E-dis_v\) 是定值，于是把 dp 转化到分层图上。

在分层图上拓扑 dp，答案就是 \(\sum_{i=0}^k f[n][i]\)。

我比较懒，直接把每个状态 \((u,i)\) 新建了点（结果跑的巨慢）。

无解情况

注意拓扑完如果仍有点未入队，证明有 0 环。

0 环一直跑下去，方案数肯定无穷啊。

但是我们看下面这个图：

有解的路径并没有经过 0 环，也就是我们应该去掉不在有解路径上的边。

判一下是否 \(dis_{1,u}+val_E+dis_{v,n}\le dis_{1,n}+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
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;

namespace RenaMoe {
template <typename TT> inline void read(TT &x) {}

const int N = 2e5 + 9;
const int K = 60;
const int INF = 0x3f3f3f3f;

struct Edge {
    int nxt, to, val;
};
struct Data {
    int id, dis;
    Data() {}
    Data(int x, int d) : id(x), dis(d) {}
    bool operator <(const Data &t) const {
        return dis > t.dis;
    }
};

int T, n, m, kk, mod, cnte;
int ex[N], ey[N], ew[N], head[N*K], dis1[N], disn[N], out[N*K], ans[N*K], q[N*K];
Edge e[N*K];
bool vis[N];
priority_queue<Data> heap;

inline void add_edge(int u, int v, int w) {
    e[++cnte] = (Edge){head[u], v, w}, head[u] = cnte;
}

inline void init() {
    cnte = 0;
    memset(head, 0, sizeof head);
    memset(out, 0, sizeof out);
    memset(ans, 0, sizeof ans);
}

// 分层图编号
inline int id(int x, int k) {
    return k * n + x;
}

inline void Dijkstra(int s, int *dis) {
    for (int i = 1; i <= n; ++i)
        dis[i] = INF, vis[i] = false;
    dis[s] = 0;
    heap.push(Data(s, 0));
    while (!heap.empty()) {
        int u = heap.top().id;
        heap.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u], v; i; i = e[i].nxt) {
            v = e[i].to;
            if (dis[v] > dis[u] + e[i].val) {
                dis[v] = dis[u] + e[i].val;
                heap.push(Data(v, dis[v]));
            }
        }
    }
}

inline void main() {
    read(T);
    while (T--) {
        init();
        read(n), read(m), read(kk), read(mod);
        for (int i = 1; i <= m; ++i)
            read(ex[i]), read(ey[i]), read(ew[i]);

        // 处理最短路
        for (int i = 1; i <= m; ++i)
            add_edge(ex[i], ey[i], ew[i]);
        Dijkstra(1, dis1);
        memset(head, 0, sizeof head), cnte = 0;
        for (int i = 1; i <= m; ++i)
            add_edge(ey[i], ex[i], ew[i]);
        Dijkstra(n, disn);
        memset(head, 0, sizeof head), cnte = 0;

        // 去掉不在有解路径上的边
        int tm = 0;
        for (int i = 1; i <= m; ++i) {
            if (dis1[ex[i]] + ew[i] + disn[ey[i]] <= dis1[n] + kk)
                tm++, ex[tm] = ex[i], ey[tm] = ey[i], ew[tm] = ew[i];
        }
        m = tm;
        // 建出分层图
        for (int i = 1; i <= m; ++i) {
            int dt = dis1[ex[i]] + ew[i] - dis1[ey[i]];
            int u = id(ex[i], 0), v = id(ey[i], dt);
            for (int j = 0; j + dt <= kk; ++j) {
                add_edge(u, v, 0), out[v]++;
                u += n, v += n;
            }
        }
        int tot = id(n, kk), sum = 0, sum_ans = 0;
        // 拓扑dp
        int l = 1, r = 0;
        for (int i = 1; i <= tot; ++i)
            if (!out[i]) q[++r] = i;
        ans[id(1, 0)] = 1;
        while (l <= r) {
            int u = q[l++];
            sum++;
            for (int i = head[u], v; i; i = e[i].nxt) {
                v = e[i].to;
                ans[v] = (ans[v] + ans[u]) % mod;
                if (!(--out[v]))
                    q[++r] = v;
            }
        }
        if (sum != tot)	
            puts("-1"); // 有0环
        else {
            for (int i = 0; i <= kk; ++i)
                sum_ans = (sum_ans + ans[id(n, i)]) % mod;
            printf("%d\n", sum_ans);
        }
    }
}
}

int main() {
    RenaMoe::main();
    return 0;
}