Luogu3953 [NOIp2017 提高组] 逛公园

tony102

2021 年 09 月 17 日

1961 次浏览

暂无评论

827字数

题解

[Link](https://www.luogu.com.cn/problem/P3953)

这应该是我第一次参加 NOIp 吧，但是马上就要迎来最后一次了

当年的题目在现在看来不仅不失先进反而显得更加优秀。

## Sol

$K = 0$ 这一档只需要跑普通最短路计数就可以了，这是考场上应该很轻松拿到的部分分。

在考虑这个问题之前，我觉得应该先考虑一下 $0$ 边带来的效果是什么？

应该很容易想到 $0$ 边肯定可以破坏是不是有无数个解，加入 $0$ 边构成了一个环，那么就有无数个解。

设从 $1$ 到 $u$ 的最短路为 $dis_{u}$ 。

观察到 $K \leq 50$  ，假如到达 $v$ 的最短路变成了 $dis_{v} + j (j \in [0,K])$  ，使我们想到设状态 $f_{i,j}$ 表示到达 $i$ 这个点距离为 $dis_i + j$ 的方案数。对于一条边 $(u, v, w)$ ，现在从 $u \to v$ 的路径长度就变成了 $dis_{u} + j + w - dis_{v}$。那么判断转移是否合法的条件就是这个东西要 $<= dis_v + K$

对于 $0$ 边的处理手段，可以给每一个经过的点打上标记，如果重复到一个点的时候这个点有标记了，说明有 $0$ 环，直接退出 `puts("1")` 即可。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef pair < int, int > PII;
typedef std::vector < PII > vec;
typedef long long LL;
const int SIZE = 1e5 + 5;
const int inf = 0x7f7f7f7f;

int n, m, k, p;
int vis[SIZE], dis[SIZE], stk[SIZE][50]; LL f[SIZE][55];
vec g[SIZE], r[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

void init() {
    for (int i = 1; i <= n; ++ i) g[i].clear(), r[i].clear(), vis[i] = 0;
    memset(dis, 0x7f, sizeof(dis)), memset(f, -1, sizeof(f));
}

void dijkstra() {
    std::priority_queue < PII > q;
    dis[1] = 0, q.push((PII) {0, 1});
    while (!q.empty()) {
        PII head = q.top(); q.pop(); int u = head.second, v;
        if (vis[u]) continue;
        vis[u] = 1;
        for (PII it: g[u]) {
            v = it.first;
            if (dis[v] > dis[u] + it.second) dis[v] = dis[u] + it.second, q.push((PII) {-dis[v], v});
        }
    }
}

LL dp(int u, int ret) {
    LL ans = 0;
    if (ret < 0 || ret > k) return 0ll;
    if (stk[u][ret]) return stk[u][ret] = 0, -1ll;
    if (f[u][ret] != -1) return f[u][ret];
    stk[u][ret] = 1;
    for (PII it: r[u]) {
        int v = it.first, d = dis[u] + ret - it.second - dis[v];
        LL res = dp(v, d); 
        if (res == -1) return stk[u][ret] = 0, -1ll;
        ans = (ans + res) % p;
    }
    stk[u][ret] = 0;
    if (u == 1 && ret == 0) ++ ans;
    return f[u][ret] = ans;
}

void sol() {
    init();
    n = read(), m = read(), k = read(), p = read();
    for (int i = 1, u, v, d; i <= m; ++ i) {
        u = read(), v = read(), d = read();
        g[u].emplace_back((PII) {v, d}), r[v].emplace_back((PII) {u, d});
    }
    dijkstra(); 
    LL ans = 0;
    for (int i = 0; i <= k; ++ i) {
        LL res = dp(n, i);
        if (res == -1) return puts("-1"), void();
        ans = (ans + res) % (1ll * p);
    }
    printf("%lld\n", ans);
}

int main() {
    int cases = read();
    while (cases -- ) sol();
    return 0;
}
```

最后修改：2021 年 09 月 17 日