P3953 逛公园

问题描述

策策同学特别喜欢逛公园。公园可以看成一张$N$个点$M$条边构成的有向图，且没有自环和重边。其中1号点是公园的入口，$N$号点是公园的出口，每条边有一个非负权值，代表策策经过这条边所要花的时间。

策策每天都会去逛公园，他总是从1号点进去，从$N$号点出来。策策喜欢新鲜的事物，他不希望有两天逛公园的路线完全一样，同时策策还是一个特别热爱学习的好孩子，他不希望每天在逛公园这件事上花费太多的时间。如果1号点到$N$号点的最短路长为$d$，那么策策只会喜欢长度不超过$d+K$路线。

策策同学想知道总共有多少条满足条件的路线，你能帮帮他吗？

为避免输出过大，答案对P取模。

如果有无穷多条合法的路线，请输出−1。

输入格式

第一行包含一个整数$T$，代表数据组数。

接下来$T$组数据，对于每组数据：

第一行包含四个整数$N,M,K,P$每两个整数之间用一个空格隔开。

接下来M行，每行三个整数$a_i,b_i,c_i$，代表编号为$a_i,b_i$的点之间有一条权值为$c_i$的有向边，每两个整数之间用一个空格隔开。

输出格式

输出文件包含$T$行，每行一个整数代表答案。

数据规模与约定

对于不同的测试点，我们约定各种参数的规模不会超过如下

对于 100%的数据, $1\le P \le 10^9,1\le a_i,b_i \le N, 0\le c_i \le 1000$。

数据保证：至少存在一条合法的路线。

记忆化搜索真是太优雅了，除了需要判一下第0层过1点的边

正题：

其实基本应该都可以猜到正解的复杂度应该是$O(NKT)$的

有向图代表我们可以按一定的顺序进行$DP$

而边权又都是整数，妥妥的把多走的路$k$和节点压进状态转移方程

我们先不考虑0环

$dp[i][j]$代表在点$j$时多走$i$的路程的方案数。

为什么特意把$i$放在第一维？因为$i$相当于那个大的循环，把$i$做完了才做$i+1$

这和平常不建多层图的分层图（即在跑最短路的时候维护$dis[i][j]$数组，代表$i$节点$j$层的信息）做法并不一样，因为那种分层图可以直接按权值大小来或者多次松弛

转移方程:$dp[i][v]=\sum dp[i+dis[v]-edge[u][v]-dis[u]][u]$

当然，我们的记忆化搜索得倒着做

我们得把每一层的$j$都分别做一遍，这样，正环也是没有影响的

0环呢？

我们维护一个搜索树的栈，代表这个点和深度的二元组还在搜索树中，如果这个二元组在搜索树中的时候又被访问，则存在0环。

值得一提的是，这样在第0层时是有问题的，它判不出来过1点的0环，需要特判

Code：

#include 
    
     #include 
     
      #include 
      
       #define P pair 
       
        using namespace std;const int N=100010;int head[N],edge[N<<2],to[N<<2],Next[N<<2],cnt;void add(int u,int v,int w){    edge[++cnt]=w;to[cnt]=v;Next[cnt]=head[u];head[u]=cnt;}int read(){    int x=0;char c=getchar();    while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}    return x;}int n,m,k,p,t,dp[52][N],dis[N],used[N],vis[52][N],to0[N];priority_queue 
        
         ,greater 
          > q;P p0;void disj(){ memset(dis,0x3f,sizeof(dis)); memset(used,0,sizeof(used)); dis[1]=0; p0.first=0,p0.second=1; q.push(p0); while(!q.empty()) { int u=q.top().second; q.pop(); if(used[u]) continue; used[u]=1; for(int i=head[u];i;i=Next[i]) { if(i&1) continue; int v=to[i],w=edge[i]; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; p0.first=dis[v],p0.second=v; q.push(p0); } } }}void init(){ memset(head,0,sizeof(head)); cnt=1; n=read(),m=read(),k=read(),p=read(); int u,v,w; for(int i=1;i<=m;i++) { u=read(),v=read(),w=read(); add(u,v,w),add(v,u,w); } disj(); memset(dp,-1,sizeof(dp));}int flag=0;void dfs0(int now){ vis[0][now]=1; for(int i=head[now];i;i=Next[i]) if((i&1)&&!edge[i]) { if(vis[0][to[i]]) {flag=1;return;} dfs0(to[i]); } vis[0][now]=0;}int dfs(int now,int rest){ if(vis[rest][now]) return -1; if(~dp[rest][now]) return dp[rest][now]; vis[rest][now]=1; int v,w,res; for(int i=head[now];i;i=Next[i]) { if(i&1) { v=to[i],w=edge[i]; res=dis[now]+rest-dis[v]-w; if(res>=0) { if(dfs(v,res)==-1) return -1; (dp[rest][now]+=dfs(v,res))%=p; } } } vis[rest][now]=0; return ++dp[rest][now];}void work(){ memset(vis,0,sizeof(vis)); int ans=0; dp[0][1]=1;dfs0(1);flag=0; if(flag) {printf("-1\n");return;} for(int i=0;i<=k;i++) { dp[i][n]=dfs(n,i); if(!(~dp[i][n])) {printf("-1\n");return;} (ans+=dp[i][n])%=p; } printf("%d\n",ans);}int main(){ t=read(); while(t--) { init(); work(); } return 0;}

2018.7.10

转载于:https://www.cnblogs.com/butterflydew/p/9290340.html

你可能感兴趣的文章