P3953 [NOIP 2017 提高组] 逛公园 题解
题目传送门
我的博客
前言
笔者的做法是最短路+记忆化搜索+DP，目前没有写完其他做法。
思路
拿到这道题后笔者第一个想法是跑一个Dijkstra后直接暴搜，期望得分 \(30pts\)。
考虑如何优化。那么我们就想到了记忆化搜索。考虑一个DP。
设 \(dis_x\) 表示 \(1\) 到 \(x\) 的最短路的长度，\(dp_{x,d}\) 表示从 \(1\) 号点进入，从 \(x\) 号点出来，恰好花费 \(dis_x+d\) 时间的合法路线数。考虑到转移过程中 \(dp_{x,d}\) 可以为 \(0\)，因此初值可以赋为 \(- \infty\)。
遍历所有可以更新 \(x\) 的结点（反图上的儿子），那么 \(dp_{x,d}\) 可以由 \(dp_{y,dd}\) 转移过来。\(dd\) 求解方式如下。
\[dis_x + d = dis_y +dd +w(w为边权)
\]
则
\[dd=dis_x - dis_y + d -w
\]
初始时为 \(dp_{1,0}=1\)，答案即为 \(\sum_{i=1}^k f_{n,i}\)。
讨论有无穷多条合法的路线的情况。不难发现，当图中有 \(0\) 环的时候，就有无穷多合法路线。因此-1的判断条件即 \(1\) 到 \(n\) 的路径中是否有 \(0\) 环。
接下来判断 \(0\) 环。如果从一个点出发还能搜到这一个点，就会有无穷种答案。所以搜索的时候可以开一个 \(vis\) 数组，记录当前结点是否能由自己更新。如果它已经被搜过就返回-1。
Subtask #1,2,7：满足 \(K=0\) 的性质。这部分可以直接跑最短路计数的板子。\(\color{red}{\text{注意：这部分也要判断 0 环！}}\)
Subtask #3,4,5,8(1,2,7)：这部分没有 \(0\) 边，代表没有 \(0\) 环。
易错点
- 正反图存储后调用的时候分清楚。
- 邻接表开两倍。
- 注意 \(dp\) 数组的初值。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define int long long
#define ___ __int128
#define INF 0x3f3f3f3f3f3f3f3f
inline int Read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-48;c=getchar();}return x*f;
}
inline void Write(int x){if(x<0) {putchar('-');x=-x;}if(x>9) Write(x/10);putchar(x%10+'0');
}
const int N=1e5+10;
int T,n,m,k,mod;
int ans;struct edge{int nxt[N<<2],to[N<<2],w[N<<2];//两倍！int head[N<<1],num_Edge=0;void add_Edge(int from,int t,int ww){nxt[++num_Edge]=head[from];to[num_Edge]=t;w[num_Edge]=ww;head[from]=num_Edge;}void clear_e(){for(int i=1;i<=n;i++) head[i]=0;num_Edge=0;}
}e1,e2;//这里为了方便直接写的成员函数//dijkstra板子
int dis[N];
bool vis[N];
struct node{int id,w;bool operator < (const node &A) const {return A.w<w;}
};
priority_queue<node> q;
void dij(int s){for(int i=1;i<=n;i++) dis[i]=INF;for(int i=1;i<=n;i++) vis[i]=0;dis[s]=0;q.push((node){s,0});while(!q.empty()){int u=q.top().id;q.pop();if(vis[u]) continue;vis[u]=1;for(int i=e1.head[u];i;i=e1.nxt[i]){int v=e1.to[i],w=e1.w[i];if(dis[v]>dis[u]+w){dis[v]=dis[u]+w;q.push((node){v,dis[v]}); }}}
}
int dp[N][60];
bool v[N][60],flag;
//v,flag：判断 0 环
int dfs(int x,int d){if(flag) return 0;//已经有 0 环，停下if(d<0||d>k) return 0;//d<0 说明此时花费时间甚至比最短路时间短，不合法//d>k 说明长度已经超过 k 了，不合法if(v[x][d]) {//自己更新到自己，有 0 环flag=1;return 0;}if(dp[x][d]>-INF) return dp[x][d];//记忆化搜索v[x][d]=1;dp[x][d]=0;for(int i=e2.head[x];i;i=e2.nxt[i]){int y=e2.to[i],w=e2.w[i];int dd=dis[x]+d-dis[y]-w;dp[x][d]+=dfs(y,dd);dp[x][d]%=mod;//转移}v[x][d]=0;return dp[x][d];
}
void init(){//多测清空！！e1.clear_e();e2.clear_e();//清空！ans=0;for(int i=0;i<N-5;i++){for(int j=0;j<55;j++){dp[i][j]=-INF;v[i][j]=0;}}flag=0;
}
void solve(){init();n=Read();m=Read();k=Read();mod=Read();while(m--){int x=Read(),y=Read(),z=Read();e1.add_Edge(x,y,z);e2.add_Edge(y,x,z);//反图}dij(1);//最短路dfs(1,0);//判断 0 环dp[1][0]=1;//初值for(int i=0;i<=k;i++){ans+=dfs(n,i);ans%=mod;}if(flag) puts("-1");else printf("%lld\n",ans);
}
signed main(){T=Read();while(T--){solve();//多测函数好！！}return 0;
}