洛谷P3953 逛公園（NOIp2017）

最短路 記憶化搜尋

題目傳送門

考場上用最短路優化一下就有60了。。。

先刷一遍反圖最短路求出每個點到 n n n的最短路 d i s [ i ] dis[i] dis[i]。

記 f [ i ] [ j ] f[i][j] f[i][j]表示到第 i i i個點，超出最短路的路程 ≤ j \leq j ≤j的方案數。搜尋的時候對每條邊的轉移 f [ i ] [ j ] = ∑ f [ v ] [ j − d ] f[i][j]=\sum f[v][j-d] f[i][j]=∑f[v][j−d]。其中 d = d i s [ v ] − d i s [ i ] + w d=dis[v]-dis[i]+w d=dis[v]−dis[i]+w。判0環的話就記錄一下目前狀态有沒有在通路路徑上即可。

代碼：

#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define F inline
using namespace std;
struct P{ int x,d; };
struct edge{ int nxt,to,d; }ed[N<<2];
int n,m,k,p,K,d[N],h1[N],h2[N],f[N][55];
priority_queue<P> q; bool v[N][55];
F char readc(){
	static char buf[100000],*l=buf,*r=buf;
	if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
	return l==r?EOF:*l++;
}
F int _read(){
	int x=0; char ch=readc();
	while (!isdigit(ch)) ch=readc();
	while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
	return x;
}
#define add(h,x,y,z) ed[++k]=(edge){h[x],y,z},h[x]=k
F bool operator <(P a,P b){ return a.d>b.d; }
F void Dij(){
	while (!q.empty()) q.pop();
	for (q.push((P){n,d[n]=0});!q.empty();q.pop()){
		int x; if (q.top().d>d[x=q.top().x]) continue;
		for (int i=h2[x],v;i;i=ed[i].nxt)
			if (d[v=ed[i].to]>d[x]+ed[i].d)
				d[v]=d[x]+ed[i].d,q.push((P){v,d[v]});
	}
}
int dfs(int x,int k){
	if (v[x][k]) return -1; if (f[x][k]) return f[x][k];
	v[x][k]=true,f[x][k]+=(x==n);
	for (int i=h1[x],v,w;i;i=ed[i].nxt)
		if ((w=d[v=ed[i].to]-d[x]+ed[i].d)<=k)
			if (dfs(v,k-w)==-1) return -1;
			else (f[x][k]+=f[v][k-w])%=p;
	return v[x][k]=false,f[x][k];
}
int main(){
	for (int t=_read();t;t--){
		n=_read(),m=_read(),K=_read(),p=_read(),k=0;
		for (int i=1;i<=n;i++) h1[i]=h2[i]=0,d[i]=1e9;
		for (int i=1;i<=n;i++)
			for (int j=0;j<=K;j++) f[i][j]=v[i][j]=0;
		for (int i=1,x,y,z;i<=m;i++){
			x=_read(),y=_read(),z=_read();
			add(h1,x,y,z),add(h2,y,x,z);
		}
		Dij(),printf("%d\n",dfs(1,K));
	}
	return 0;
}