【题解】NOIP2017逛公园(DP)

第一次交挂了27分...我是不是必将惨败了...

考虑这样一种做法，设\(d_i\)表示从该节点到n节点的最短路径，\(dp(i,k)\)表示从\(i\)节点到\(n\)多走至多\(k\)距离的方案数。转移相当于枚举走哪条边，状态的变化是如果走这条边会比最短路多多少。

转移方程

\[dp(i,k) =\sum_{(i,u,w)\in E} dp(u,k-(w-(d_i-d_u))
\]

直接用dfs实现转移(记得判环)即可。

...

但是我们不能这么敷衍，转移顺序究竟是什么？

可以这样理解：反向跑最短路后，可以建成一个新图\(G'=(V,E)\)其中，\(E\)的原图边的子集，且对于边\((u,v)\)当且仅当\(d_u \ge d_v\)时存在(d是反向最短路数组)。这个新图若非DAG则无解/无限解。所以现在保证是个DAG了，所以拓扑排序之后可以转移了。(存在一个)拓扑排序就是DFS回溯顺序。

时间复杂度\(O(T(mk+nk+n\log m))\)。合法\(0\)边越多越能顶到这个复杂度。

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=1e5+5;

template<class M>

struct HEAP{

      M data[maxn*2];

      int cnt;

      inline void down(const int&pos){

	    for(int t=pos,k;(t<<1)<=cnt;t=k){

		  k=t<<1;

		  if(k<cnt&&data[k|1]<data[k]) k|=1;

		  if(data[t]>data[k]) swap(data[t],data[k]);

		  else return;

	    }

      }

      inline void up(const int&pos){

	    for(int t=pos;t>>1;t>>=1)

		  if(data[t]<data[t>>1]) swap(data[t],data[t>>1]);

		  else return;

      }

      inline void push(const M&x){data[++cnt]=x,up(cnt);}

      inline void pop(){swap(data[1],data[cnt--]);down(1);}

      inline M top(){return data[1];}

      inline int size(){return cnt;}

};

HEAP< pair<int,int> > q;

struct E{

      int to,nx,w;

      E(){to=nx=w=0;}

      E(const int&x,const int&y,const int&z){to=x; nx=y; w=z;}

}e[maxn<<2];

int head[maxn],cnt,head0[maxn];

inline void add(const int&fr,const int&to,const int&w,int*h=head){e[++cnt]=E(to,h[fr],w),h[fr]=cnt;}

int d[maxn],n,m,k,mod;

typedef pair<int,int> P;

const int inf=1e9;

inline void dij(){

      for(int t=1;t<=n;++t) d[t]=inf;

      q.push((P){d[n]=0,n});

      while(q.size()){

	    P now=q.top(); q.pop();

	    if(now.first>d[now.second]) continue;

	    for(int t=head[now.second];t;t=e[t].nx)

		  if(d[e[t].to]>d[now.second]+e[t].w)

			q.push((P){d[e[t].to]=d[now.second]+e[t].w,e[t].to});

      }

}

int dp[55][maxn];

bool usd[55][maxn];

bool in[55][maxn];

int dfs(const int&now,const int&k){

      if(in[k][now])return -1;

      if(usd[k][now]) return dp[k][now];

      dp[k][now]=now==n;

      in[k][now]=usd[k][now]=1;

      for(int t=head0[now];t;t=e[t].nx){

	    int g=e[t].w-(d[now]-d[e[t].to]),ret;

	    if(g>k)continue;

	    if(ret=dfs(e[t].to,k-g),-1==ret) return dp[k][now]=-1;

	    dp[k][now]=(dp[k][now]+ret)%mod;

      }

      in[k][now]=0;

      return dp[k][now];

}

int main(){

      int T=qr();

      while(T--){

	    cnt=0;

	    n=qr(); m=qr(); k=qr(); mod=qr();

	    for(register int t=0;t<=n;++t) head[t]=head0[t]=0;

	    for(int i=0;i<=k;++i)

		  for(register int t=0;t<=n;++t)

			dp[i][t]=usd[i][t]=in[i][t]=0;

	    for(int t=1,t1,t2,t3;t<=m;++t)

		  t1=qr(),t2=qr(),t3=qr(),add(t2,t1,t3),add(t1,t2,t3,head0);

	    dij();

	    //for(int t=1;t<=n;++t) printf("%d\n",d[t]);

	    printf("%d\n",dfs(1,k));

      }

      return 0;

}

巴特西

【题解】NOIP2017逛公园(DP)

【题解】NOIP2017逛公园(DP)

最新文章

热门文章