#C241003B. [NOIP2017 提高组] 逛公园

标签（Label）

• 动态规划
• 最短路算法
• 逆向思维
• 记忆化搜索

网址（Website）

P3953 [NOIP2017 提高组] 逛公园 - 洛谷

题解（Solution）

$\qquad$发现 $k \le 50$ ，考虑动态规划。

$\qquad$ 由于涉及最短路，先对反图跑一次 $\mathrm{dijkstra}$ ，求出每个点到 $n$ 的最短距离，令 $f[x][k]$ 表示第 $x$ 个点，当前路径比最小值大 $k$ ，考虑转移： $f[x][k] \leftarrow f[y][k + \text{dis}[x] - \text{dis}[y] - w]$ ，其中，$\text{dis}[x]$ 和 $\text{dis}[y]$ 分别表示点 $x$ 和点 $y$ 到 $n$ 的最短距离，$w$ 表示点 $x$ 和点 $y$ 之间边权。

$\qquad$可以使用记忆化搜索来优化时间复杂度。

$\qquad$现在考虑如何判断零环，用一个 $vst[x][k]$ 数组记录有没有到过点为 $x$ ，路径长度比最小值多 $k$ 这个状态，如果发现再次到达这个状态，那么输出 $-1$ 。

$\qquad$时间复杂度 $O(KM)$ 。

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#include<bitset>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 101234;
const int K = 64;
bool ST;

vector<P> ft[N], rt[N];
int n,m,k,p,ans;

inline void add(int &x,int y){if((x+=y)>=p) x-=p;}

int dis[N];
void dijkstra(int st){
	memset(dis, 0x3f, sizeof dis[0]*(n+5));
	priority_queue<P> q;
	q.emplace(0,st), dis[st] = 0;
	while(q.size()){
		int x = q.top().y, d = -q.top().x;q.pop();
		if(dis[x] < d) continue;
		for(auto p:rt[x]){
			int y = p.x, v = p.y;
			if(dis[x]+v < dis[y]){
				dis[y] = dis[x] + v;
				q.emplace(-dis[y], y);
			}
		}
	}
}

bitset<K> vst[N];
int f[N][K];
bool fail;
inline int dfs(int x, int j){
	if(j < 0) return 0;
	if(vst[x][j]) return fail = true, 0;
	if(f[x][j]) return f[x][j];
	vst[x][j] = true;
	int res = 0;
	for(auto p:ft[x]){
		int y = p.x, w = p.y;
		add(res, dfs(y, j+dis[x]-dis[y]-w));
		if(fail) return 0;
	}
	vst[x][j] = false;
	return f[x][j] = res;
}

inline void solve(){
	n = rd(), m = rd(), k = rd(), p = rd();
	
	For(i,1,m){
		int x = rd(), y = rd(), v = rd();
		ft[x].emplace_back(y,v);
		rt[y].emplace_back(x,v);
	}dijkstra(n);
	
	dfs(n,0);//提前判断零环，防止下一行直接返回忽略掉 
	f[n][0] = 1, ans = 0;
	For(i,0,k) add(ans, dfs(1,i));
	cout<<(fail ? -1 : ans)<<'\n';
	
	For(i,1,n){	
		ft[i].clear(),rt[i].clear(),vst[i].reset(),
		memset(f[i], 0, sizeof f[i][0]*(k+5));
	}fail = false;
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = rd(), Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}