「NOIP2017」 逛公园

发表于 更新于 分类于

「NOIP2017」 逛公园

题目

策策同学特别喜欢逛公园。公园可以看成一张\(N\)个点\(M\)条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，\(N\)号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。 策策每天都会去逛公园，他总是从1号点进去，从\(N\)号点出来。

策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果1号点到\(N\)号点的最短路长为\(d\)，那么策策只会喜欢长度不超过\(d+k\)的路线。策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？为避免输出过大，答案对\(P\)取模。如果有无穷多条合法的路线，请输出-1。

分析

首先需要最短路处理出\(1\)和\(n\)作为起点到每个点的最短路。

有无数解的情况是有零环并且走零环能满足长度不大于\(d+k\)的条件。

\(k\)的范围应该很\(dp\)，就是\(f[i][k]\)表示走到\(i\)点，相对最短路多走了\(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
#include <bits/stdc++.h>
using namespace std;

const int N = 100004;
struct E {int nxt, v, w;} e1[N << 1], e2[N << 1];
int n, m, head1[N], dis1[N], head2[N], dis2[N], ecnt1, ecnt2, k, MOD, qp[N], tot, d[N], f[55][N];
queue<int> q;
bool book[N];

void add-edge(int u, int v, int w) {
    e1[++ecnt1] = {head1[u], v, w}; head1[u] = ecnt1;
    e2[++ecnt2] = {head2[v], u, w}; head2[v] = ecnt2;
}

void upd(int &x, int y) {
    x = x + y;
    if (x >= MOD) x -= MOD;
}

void solve() {
    ecnt1 = ecnt2 = 0;
    memset(dis1, 0x3f, sizeof dis1);
    memset(dis2, 0x3f, sizeof dis2);
    memset(head1, 0, sizeof head1);
    memset(head2, 0, sizeof head2);
    scanf("%d %d %d %d", &n, &m, &k, &MOD);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        add-edge(u, v, w);
    }
    // dij
    priority-queue<pair<int, int> > q;
    dis1[1] = 0;
    memset(book, 0, sizeof book);
    q.push({0, 1});
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (book[u]) continue;
        book[u] = 1;
        for (int i = head1[u]; i; i = e1[i].nxt) {
            int v = e1[i].v, w = e1[i].w;
            if (dis1[u] + w < dis1[v]) {
                dis1[v] = dis1[u] + w;
                q.push({-dis1[v], v});
            }
        }
    }
    dis2[n] = 0;
    memset(book, 0, sizeof book);
    q.push({0, n});
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (book[u]) continue;
        book[u] = 1;
        for (int i = head2[u]; i; i = e2[i].nxt) {
            int v = e2[i].v, w = e2[i].w;
            if (dis2[u] + w < dis2[v]) {
                dis2[v] = dis2[u] + w;
                q.push({-dis2[v], v});
            }
        }
    }
    memset(d, 0, sizeof d);
    tot = 0;
    for (int i = 1; i <= n; i++)
        for (int j = head1[i]; j; j = e1[j].nxt) {
            int v = e1[j].v, w = e1[j].w;
            if (dis1[i] + w == dis1[v]) d[v]++;
        }
    for (int i = 1; i <= n; i++) if (d[i] == 0) qp[++tot] = i;
    for (int i = 1; i <= tot; i++) {
        int u = qp[i];
        for (int j = head1[u]; j; j = e1[j].nxt) {
            int v = e1[j].v, w = e1[j].w;
            if (dis1[v] == dis1[u] + w) {
                d[v]--;
                if (d[v] == 0) qp[++tot] = v;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (d[i] && dis1[i] + dis2[i] <= dis1[n] + k) {
            puts("-1");
            return;
        }
    }
    memset(f, 0, sizeof f);
    f[0][1] = 1;
    for (int l = 0; l <= k; l++) {
        for (int i = 1; i <= tot; i++) {
            int u = qp[i];
            for (int j = head1[u]; j; j = e1[j].nxt) {
                int v = e1[j].v, w = e1[j].w;
                if (dis1[v] == dis1[u] + w) upd(f[l][v], f[l][u]);
            }
        }
        for (int u = 1; u <= n; u++) {
            for (int j = head1[u]; j; j = e1[j].nxt) {
                int v = e1[j].v, w = e1[j].w;
                if (dis1[v] != dis1[u] + w && l + dis1[u] + w - dis1[v] <= k) {
                    upd(f[l + dis1[u] + w - dis1[v]][v], f[l][u]);
                }
            }
        }
    }
    int res = 0;
    for (int i = 0; i <= k; i++) upd(res, f[i][n]);
    printf("%d\n", res);
    return;
}

int main() {
    int -;
    for (scanf("%d", &-); -; ---) solve();
    return 0;
}