P3953 [NOIP2017 提高组] 逛公园

P3953 [NOIP2017 提高组] 逛公园

总算把咕了快四年的题A了QAQ。

题意

给出 $N, M, K, P$，一个包含 $N$ 个点 $M$ 条边的有向图，没有自环和重边，顶点编号从 $1\sim N$。

令 $dis(u, v)$ 为从 $u$ 出发到达 $v$ 的最短路径，求从顶点 $1$ 到顶点 $N$ 的路程小于等于 $dis(1, N) + K$ 的路径数目。

答案对 $P$ 取模。

思路

计数问题又可以考虑dp了，先用dijkstra算法求出顶点 $1$ 到每个顶点的最短距离。

设 $f(u, j)$ 表示，从顶点 $1$ 到顶点 $u$ 距离满足小于等于 $dis(1, u)+j$ 的路径数目，$j$ 也就是当前距离和最短距离在容许范围内的最大差值。

考虑一条有向边 $(u, v)$，边权为 $w_{u,v}$，则转移为：

$$f(v, dis(1, u) + j + w_{u, v} - dis(1, v)) += f(u, j)$$

其中 $dis(1, u) + j + w_{u, v} - dis(1, v)$ 表示在 $dis(1, u) + j$ 的基础上加上权值 $w_{u,v}$ 后获得的总距离，再和最短距离 $dis(1, v)$ 做差获得差值，当差值非负的时候就能进行转移。

由于上式不好直接正推出来，所以考虑记忆化搜索实现dp的转移，于是将上式改写成：

$$f(u, j) += f(v, j + dis(1, u) - dis(1, v) - w_{v, u})$$

于是先反向建图，然后在反向图中进行记忆化搜索即可。

关于零环的判断，只要在记忆化搜索中，判断 $f(u, j)$ 有没有在同一次搜索中出现两次即可，因为如果出现两次，当且仅当通过路程上的点的最短距离都相等，且边权值都为0，这就一定是0环了。

而且这样不会被卡数据，因为这不是直接去找0环，而是在满足 $j\geqslant 0$ 的前提下去找的，这样就保证了这个0环一定是可以到达的。

解释一下可以到达的含义：如果 $K$ 特别小，比如是 $K=0$，如果在1到N的最短路外出现了一个零环，对答案是没有任何影响的，因为你根本走不到这个位置。

注： 构造了一个特殊原点编号为0，它向顶点1连接一条边权为0的有向边，这样在记忆化搜索中，就不会找到 $f(1, 0)$ 就提前返回了，而没有判断顶点1是否是在0环中。

初始化：$f(0,0)= 0$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
//#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
struct Edge {
	int v, w;
};
int n, m, K, P;
bool fg;
vi dis;
vii f, vis;
void dijkstra(vector<vector<Edge>> &E) {
	priority_queue<pii, vp, greater<pii>> q;
	dis = vi(n+1, INF);
	vi vis(n+1);
	dis[0] = 0;
	q.push({0, 0});
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for (auto e : E[u]) {
			if (dis[e.v] - dis[u] > e.w) {
				dis[e.v] = dis[u] + e.w;
				q.push({dis[e.v], e.v});
			}
		}
	}
}
int rec(vector<vector<Edge>> &E, int u, int j) {
	if (vis[u][j]) {
		fg = 1;
		return 0;
	}
	if (f[u][j] != -1) return f[u][j];
	f[u][j] = 0, vis[u][j] = 1;
	for (auto e : E[u]) {
		int k = j + dis[u] - dis[e.v] - e.w;
		if (k < 0) continue;
		f[u][j] = (f[u][j] + rec(E, e.v, k)) % P;
	}
	vis[u][j] = 0;
	return f[u][j];
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m >> K >> P;
		fg = 0;
		f = vii(n+1, vi(K+1, -1));
		vis = vii(n+1, vi(K+1));
		vector<vector<Edge>> E1(n+1), E2(n+1);
		for (int i = 0; i < m; i++) {
			int u, v, w;
			cin >> u >> v >> w;
			E1[u].pb({v, w}); //E1存正向边
			E2[v].pb({u, w}); //E2存反向边
		}
		E1[0].pb({1, 0});
		E2[1].pb({0, 0});
		dijkstra(E1);
		int ans = 0;
		f[0][0] = 1;
		for (int i = 0; i <= K; i++) {
			ans = (ans + rec(E2, n, i)) % P;
		}
		if (fg) ans = -1;
		cout << ans << '\n';
	}
	return 0;
}