2 条题解
-
2
考虑一种最简单的状态
设 为走到点 路线长度恰为 的方案数。转移则是枚举从哪个点走过来。
即 设 边权为
这么做的状态是非常多的,但是我们可以发现有一个 的限制,导致很多第二维状态没有用处。例如设 的最短路为
对于 的状态 必然为 ,实际需要求的也仅仅是 只有 个状态是合法的
对于其余的某个点 设到达点 的最短路是 则 必须
同时必须满足
简单证明来说,若走到 第二维 已经大于 则后续不管怎么走走到 的路径长度必然大于
故而对于任意点 只需要考虑 个状态。
重新修改状态,设 为从起点走到 且路径长度恰好为 的所有路线数量,相当于第二维是最短距离加偏移量。
状态转移:由于第二维寸的是一个偏移量,考虑某个点 走到 ,点 此时第二维状态 ,实际走到 的真实距离是 则走到 的真是距离应为 ,它同时等于 , 为此时走到 的便宜量,则 。即 。
若有环怎么办?
首先对于本题来说,如果存在一条路径走到 有环,环上边权和为 那么肯定有无限种方案,因此在使用记忆化搜索的同时若出现循环依赖,直接返回负 即可。
具体步骤
- 使用最短路算法预处理最短路
- 记忆化搜索搜索
- 记忆化搜索可以存反图,从终点开始搜索,这是为了保证求解的正确性,因为图中的某些点不一定能到达 假如走到一个环,且该环无法到达 则导致了后续求解的错误。
- 对于判断是否存在 的环路,则看一个状态是否重复访问即可,设置一个判重数组来判断状态是否重复访问。
#include <bits/stdc++.h> #define ll long long #define p pair<int, int> #define x first #define y second using namespace std; const int N = 1e5 + 5; int n, m, k, mod, d[N], f[N][55]; vector<p> e[N], ne[N]; bool vis[N], flag; bool instk[N][55]; void dijkstra() { memset(d, 0x3f, sizeof(d)); memset(vis, 0, sizeof(vis)); priority_queue<p, vector<p>, greater<p>> q; q.push({0, 1}); d[1] = 0; while (q.size()) { auto now = q.top(); q.pop(); int u = now.y; if (vis[u]) continue; vis[u] = 1; for (auto road : e[u]) { int v = road.x, w = road.y; if (d[v] > d[u] + w) { d[v] = d[u] + w; q.push({d[v], v}); } } } } int dp(int u, int j) // f[b][j] { if (instk[u][j]) { flag = 1; return 0; } if (f[u][j] != -1) return f[u][j]; f[u][j] = 0; if (u == 1 && j == 0) f[u][j]++; instk[u][j] = 1; for (auto road : ne[u]) { int v = road.x, w = road.y; int x = d[u] + j - w - d[v]; if (x < 0 || x > k) continue; f[u][j] = (f[u][j] + dp(v, x)) % mod; if (flag) return 0; } instk[u][j] = 0; return f[u][j]; } void solve() { cin >> n >> m >> k >> mod; for (int i = 1; i <= n; i++) e[i].clear(), ne[i].clear(); while (m--) { int u, v, w; cin >> u >> v >> w; e[u].push_back({v, w}), ne[v].push_back({u, w}); } dijkstra(); memset(f, -1, sizeof(f)); int res = 0; flag = 0; memset(instk, 0, sizeof(instk)); for (int i = 0; i <= k; i++) { res = (res + dp(n, i)) % mod; if (flag) { res = -1; break; } } cout << res << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while (t--) solve(); return 0; }
- 1
信息
- ID
- 1387
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 25
- 已通过
- 13
- 上传者