luogu3953 逛公园

题目描述

策策同学特别喜欢逛公园。公园可以看成一张$N$个点$M$条边构成的有向图,且没有 自环和重边。其中1号点是公园的入口,$N$号点是公园的出口,每条边有一个非负权值, 代表策策经过这条边所要花的时间。

策策每天都会去逛公园,他总是从1号点进去,从$N$号点出来。

策策喜欢新鲜的事物,它不希望有两天逛公园的路线完全一样,同时策策还是一个 特别热爱学习的好孩子,它不希望每天在逛公园这件事上花费太多的时间。如果1号点 到$N$号点的最短路长为$d$,那么策策只会喜欢长度不超过$d + K$的路线。

策策同学想知道总共有多少条满足条件的路线,你能帮帮它吗?

为避免输出过大,答案对$P$取模。

如果有无穷多条合法的路线,请输出$-1$。

输入格式

第一行包含一个整数 $T$, 代表数据组数。

接下来$T$组数据,对于每组数据: 第一行包含四个整数 $N,M,K,P$,每两个整数之间用一个空格隔开。

接下来$M$行,每行三个整数$a_i,b_i,c_i$,代表编号为$a_i,b_i$的点之间有一条权值为 $c_i$的有向边,每两个整数之间用一个空格隔开。

输出格式

输出文件包含 $T$ 行,每行一个整数代表答案。

样例输入

2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0

样例输出

3
-1

说明

数据范围:$T\le 5$,$N\le 10^5$,$M\le 2\times 10^5$,$K\le 50$。


分析

先预处理出点$1$到每个点的最短路$minDis(u)$。观察到$K$只有$50$,意味着对于符合条件的路径,走到每个点$u$的实际距离$dis(u)$都不会超过$minDis(u)+50$。

设$f(u,d)$表示从$1$走到$u$,且$dis(u)-minDis(u)=d$的方案数。转移可以从$f(u,t)$转移到$f(v,minDis(u)+t+w-minDis(v))$。现在主要是转移顺序的问题、

对于没有$0$边的数据点,可以直接按实际距离$dis(u)=minDis(u)+d$从小到大转移。对于有$0$边的数据点,需要拓扑排序来确定更新顺序,这个做法比较麻烦。

另一种做法是直接用记忆化搜索来自顶向下进行这个DP,就不需要考虑更新顺序了。若搜索时发现环可以直接输出$-1$。

(去年考场没想到记搜……太弱了)

代码

#include <bits/stdc++.h>

const int N = 1e5+50;
const int M = 2e5+50;
const int K = 55;

struct Graph {
    struct Edge {
        int to, nxt;
        int w;
    } e[M];
    int top, head[N];

    void clear() {
        top = 0;
        memset(head, -1, sizeof head);
    }

    Graph() {
        clear();
    }

    void add(int u, int v, int w) {
        e[top] = (Edge){v, head[u], w};
        head[u] = top++;
    }
} G, rG;

int n, m, k, p;
int dis[N];
bool vis[N];
int f[N][K];
bool in[N][K];

void add(int &x, int y) {
    x = ((x + y) % p + p) % p;
}

void spfa() {
    std::queue<int> q;
    memset(dis, 0x3f, sizeof dis);
    q.push(n);
    dis[n] = 0;
    vis[n] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = false;
        for (int i = rG.head[u]; ~i; i = rG.e[i].nxt) {
            int v = rG.e[i].to, w = rG.e[i].w;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }
    }
}

int dfs(int u, int d) {
    if (d < 0 || d > k) return 0;
    if (in[u][d]) return -1;
    if (f[u][d] != -1) return f[u][d];
    in[u][d] = true;
    int rtn = 0;
    for (int i = G.head[u]; ~i; i = G.e[i].nxt) {
        int v = G.e[i].to, w = G.e[i].w;
        int t = dfs(v, dis[u] + d - w - dis[v]);
        if (t == -1) return -1;
        add(rtn, t);
    }
    in[u][d] = false;
    if (u == n && d == 0) rtn++;
    f[u][d] = rtn;
    return rtn;
}

int work() {
    memset(f, -1, sizeof f);
    memset(in, 0, sizeof in);
    int rtn = 0;
    for (int i = 0; i <= k; i++) {
        int t = dfs(1, i);
        if (t == -1) return -1;
        add(rtn, t);
    }
    return rtn;
}

void solve() {
    scanf("%d%d%d%d", &n, &m, &k, &p);
    G.clear();
    rG.clear();
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        G.add(u, v, w);
        rG.add(v, u, w);
    }
    spfa();
    printf("%d\n", work());
}

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


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论