Noip 2017 逛公园解题报告

                                             wsndy
                                             18.05.03

题解

题面

策策同学特别喜欢逛公园。公园可以看成一张 $N$ 个点 $M$ 每条边构成的有向图，且没有 自环和重边。其中 $1$ 号点是公园的入口，$N$ 号点是公园的出口，每条边有一个非负权值， 代表策策经过这条边所要花的时间。
策策每天都会去逛公园，他总是从 $1$ 号点进去，从 $N$ 号点出来。
策策喜欢新鲜的事物，它不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，它不希望每天在逛公园这件事上花费太多的时间。如果 $1$ 号点到 $N$ 号点的最短路长为 $d$ ，那么策策只会喜欢长度不超过 $d + K$ 的路线。
策策同学想知道总共有多少条满足条件的路线，你能帮帮它吗？
为避免输出过大，答案对 $P$ 取模。
如果有无穷多条合法的路线，请输出 $−1$。

---

题意

给出一张带权有向图，可能有 $0$ 边，问从 $1$ 号点到n号点长度不超过最短路长度 $+k$ 的路径有几条，若有无穷多条输出 $-1$。

---

数据范围

$$n<={10^3}/{10^5},m<=2n,k=0/<=50;$$

---

分析

什么时候会有无穷多条？
存在一条长度不超过 $d+k$ 的路径，上面可以套一个 $0$ 环
也就是说，只有有 $0$ 边的情况才可能有无穷多条

---

Task1

$k=0$
如果不存在 $0$ 边，就是一个很经典的dp了
设 $d_{i}$ 为 $1$ 号点到 $i$ 号点的最短路，$f_{i}$ 为最短路条数

$$f_{i} = \sum_{}^{}f_{j},d_{j} + E_{j->i} = d_{i}$$
然后我们惊喜的发现所有 $k=0$ 的测试点都没有 $0$ 边这样就拿到的 $30$ 分

---

Task2

不存在 $0$ 边
然后我们发现这个 $k$ 非常小
尝试把 $k$ 放到状态里面去
$f_{i,j}$ 表示从 $1$ 号点到 $i$ 号点长度为 $d_{i} + j$ 的路径条数

$$f_{i,j} = \sum_{}^{}f_{x,y}, d_{x} + y + E_{x->i} = d_{i} + j$$
这个状态不是很好转移
转移图是个 $DAG!$
因为没有 $0$ 边，$f_{i} + j$ 是严格递减的，不存在环
记忆化搜索即可
时间复杂度 $O(mlog_{2}^{n} + mk)$, 可以拿到 $70$ 分

---

Task3

如果有 $0$ 边会发生什么呢？
可能会出现 $0$ 环
有 $0$ 环就一定无解吗?
显然不是
回顾一下无穷多解的条件
一条长度 $<= d + k$ 的路径套一个 $0$ 环
也就是说 $0$ 环上有一点，经过它的最短路长度 $<= d + k$
则有无穷多解
我们记录 $d_{1,i}$ 表示从 $1$ 号点出发到 $i$ 号点的最短路
$d_{2,i}$ 表示从 $i$ 号点到 $n$ 号点的最短路，可以把边反向
那么 $d_{1,i} + d_{2,i}$ 表示经过 $i$ 号点的最短路
开一个 $bool$ 数组记录下每一个 $f_{i,j}$ 是否在访问中
如果访问了一个已经在访问的说明出现了环
同时满足 $d_{1,i} + d_{2,i} + j <= d + k$ 的话就是 $-1$
当然，如果 $d_{1,i} + d_{2,i} + j >= d + k,$ 这个状态肯定用不到
直接抛弃掉即可

---

Code

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e5 + 10, K = 51;
int n, m, k, p, tot, ans = 0;
int first[N], next[N << 1], en[N << 1], w[N << 1];
int first1[N * K], next1[N * K << 1], en1[N * K << 1], d[N * K];
int q[N << 6], dis[N], dis1[N], u[N << 1], v[N << 1], t[N << 1], f[N * K];
bool bz[N];
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
inline void insert(int x, int y, int z) {
    next[++ tot] = first[x];
    first[x] = tot;
    en[tot] = y;
    w[tot] = z;
}
inline void insert1(int x, int y) {
    next1[++ tot] = first1[x];
    first1[x] = tot;
    en1[tot] = y;
    d[y] ++;
}
inline int get(int x, int y) {return (x - 1) * (k + 1) + y + 1;}
int main() {
    int T = read();
    while(T --) {
        n = read(), m = read(), k = read(), p = read();
        memset(first, tot = 0, sizeof(first));
        for(int i = 1; i <= m; i ++) {
            u[i] = read(), v[i] = read(), t[i] = read();
            insert(u[i], v[i], t[i]);
        }
        memset(dis, 60, sizeof(dis));
        int l = dis[1] = 0, r = q[1] = 1;
        while(l < r) {
            int x = q[++ l];
            bz[x] = false;
            for(int i = first[x]; i; i = next[i])
                if(dis[x] + w[i] < dis[en[i]]) {
                    dis[en[i]] = dis[x] + w[i];
                    if(! bz[en[i]]) bz[q[++ r] = en[i]] = true;
                }
        }
        memset(first, tot = 0, sizeof(first));
        for(int i = 1; i <= m; i ++) insert(v[i], u[i], t[i]);
        memset(dis1, 60, sizeof(dis1));
        l = dis1[q[r = 1] = n] = 0;
        while(l < r) {
            int x = q[++ l];
            bz[x] = false;
            for(int i = first[x]; i; i = next[i])
                if(dis1[x] + w[i] < dis1[en[i]]) {
                    dis1[en[i]] = dis1[x] + w[i];
                    if(!bz[en[i]]) bz[q[++ r] = en[i]] = true;
                }
        }
        memset(first1, tot = 0, sizeof(first1));
        memset(d, 0, sizeof(d));
        for(int i = 1; i <= m; i ++) {
            int x = get(u[i], 0), y = get(v[i], dis[u[i]] + t[i] - dis[v[i]]);
            for(int j = dis[u[i]]; j + t[i] + dis1[v[i]] <= dis[n] + k; j ++, x ++, y ++)
                insert1(x, y);
        }
        int num = (k + 1) * n, sum = 0;
        l = r = ans = 0;
        memset(f, 0, sizeof(f));
        for(int i = 1; i <= num; i ++)
            if(!d[i]) q[++ r] = i;
        f[1] = 1;
        while(l < r) {
            int x = q[++ l];
            sum ++;
            for(int i = first1[x]; i; i = next1[i]) {
                if(! -- d[en1[i]]) q[++ r] = en1[i];
                f[en1[i]] += f[x];
                f[en1[i]] = f[en1[i]] > p ? f[en1[i]] - p : f[en1[i]];
            }
        }
        if(sum < num) printf("-1\n");
        else {
            for(int i = 0; i <= k; i ++) ans = (ans + f[get(n, i)]) % p;
            printf("%d\n", ans);
        }
    }
    return 0;
}