发现 $K$ 很小,不妨设置一个 $O(NK)$ 的 $DP$。
发现可行的最短路必须满足是 $d <= dis <= d + K$。
由逆向思维,则是从某点出发,可以消耗 $K$ 个单位的冗余长度,最终到达 $n$。
如何快速的计算出有走这条边冗余长度呢
首先建反向图跑 $Dijkstra$,求出 $dis[i]$ 表示从 $i$ 到 $n$ 的最短路距离。
假设有一条边 $(u, v)$,边长为 $w$
那么我现在从 $u$ 到 $n$ 的预算距离是 $dis[v] + w$,最短距离是 $dis[u]$。
那么多走的就是 $dis[v] + w - dis[u]$。
设计 $DP$ 状态表示:
$f[i][j]$ 表示从 $i$ 到 $n$,以及消耗了 $j$ 个单位的冗余长度的方案数。
状态转移:
设有边 $(u, v)$,边长为 $w$
则有 $f[u][j] += f[v][j - (dis[v] + w - dis[u])]$。
边界 $f[n][0] = 1$,其余为 $0$。
答案 $\sum_{i = 0}^{K} f[1][i]$。
无穷解的判断:
发现有无穷解,当且仅当:
有一个总权为 $0$ 的环。
我们可以在 $DP$ 的时候搞一个 $vis$ 数组判断,就不需要单独判无穷解了。
时间复杂度
整个过程用记忆化搜索实现,由于一共有 $NK$ 个状态,每个点被枚举 $K$ 次,即每条边总体被枚举 $K$ 次。
所以复杂度 $O(K(N + M))$。
$Tips:$
- 可能走到 $n$ 再折回去,所以 $u = n $ 时不能直接 $return$
- 可能存在经过 $n$ 点的 $0$ 环,所以到 $n$ 点时顺便判一下环。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
#include <cstdlib>
using namespace std;
typedef pair<int, int> PII;
const int N = 100005, M = 400005, S = 51;
int n, m, K, P, f[N][S], dis[N];
int head[N], rhead[N], numE[2];
bool st[N], vis[N][S], ep = false;
struct E {
int next, v, w;
}e[M], r[M];
//建图
void inline add(E g[], int h[], int u, int v, int w, int p) {
g[++numE[p]] = (E) { h[u], v, w };
h[u] = numE[p];
}
//多组数据初始化
void inline init() {
ep = false;
memset(dis, 0x3f, sizeof dis);
memset(st, false, sizeof st);
numE[0] = numE[1] = 0;
memset(head, 0, sizeof head);
memset(rhead, 0, sizeof head);
memset(f, -1, sizeof f);
}
// Dijkstra 最短路
priority_queue<PII, vector<PII>, greater<PII> > q;
void inline dijkstra() {
dis[n] = 0; q.push(make_pair(0, n));
while(!q.empty()) {
PII u = q.top(); q.pop();
if(st[u.second]) continue;
st[u.second] = true;
for (int i = rhead[u.second]; i; i = r[i].next) {
int v = r[i].v;
if(dis[u.second] + r[i].w < dis[v]) {
dis[v] = dis[u.second] + r[i].w;
q.push(make_pair(dis[v], v));
}
}
}
}
//记忆化搜索
int dfs(int u, int j) {
if(vis[u][j]) { ep = true; return 0; }
if(f[u][j] != -1) return f[u][j];
vis[u][j] = true;
int &val = f[u][j] = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v, w = e[i].w;
//消耗的冗余长度折算
int k = j - (dis[v] + w - dis[u]);
if(0 <= k && k <= K) (val += dfs(v, k)) %= P;
if(ep) return 0;
}
vis[u][j] = false;
if(u == n && j == 0) val = 1;
return val;
}
int main() {
int T; scanf("%d", &T);
while(T--) {
init();
scanf("%d%d%d%d", &n, &m, &K, &P);
for (int i = 1, u, v, w; i <= m; i++) {
scanf("%d%d%d", &u, &v, &w);
add(e, head, u, v, w, 0); add(r, rhead, v, u, w, 1);
}
dijkstra();
int ans = 0;
for (int i = 0; i <= K; i++) {
memset(vis, false, sizeof vis);
(ans += dfs(1, i)) %= P;
if(ep) break;
}
if(ep) puts("-1");
else printf("%d\n", ans);
}
}
请问为什么是
而不是
以及
这里,为什么要重置为 false,
希望你能回答,谢谢
vis是当前dfs依赖的链表示正在处理吧
我是倒着退的,好像,所以确定最终答案之后越来越少
要是出现反向边 , 大概满足不了吧
这题咋满足后效性的啊QAQ
就是大概要么忘后面的层,每层内,最短路的更新结构是个dag
很久前写的,非常垃圾。。
nump又是干啥用的啊(
我傻逼了(知道了hh
不是 , 您说的层是什么啊
大概是以dp的第二维度,冤枉路相同的是一层