Tony102's Blog - 最短路
type: channel
link: https://tony102.com/index.php/tag/%E6%9C%80%E7%9F%AD%E8%B7%AF/
items: Luogu3953 [NOIp2017 提高组] 逛公园

Luogu3953 [NOIp2017 提高组] 逛公园
type: item
date: 2021-09-17T10:13:00+08:00
description: Link这应该是我第一次参加 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#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, -…