LOJ P3953 逛公园 NOIP dp 最短路 拓扑排序

https://www.luogu.org/problemnew/show/P3953

开o2过了不开o2re一个点。。。写法如题

顺便一提这道题在我校oj是a不了的因为我校土豆服务器速度奇慢1s时限

 // luogu-judger-enable-o2

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int maxn=;

 int n,m,k,p;

 struct nod{

     int y,v,next;

 }e[][maxn*];

 int head[][maxn]={};

 int dis[][maxn]={};

 int d[maxn]={},zz[maxn]={};

 int mx,cnt=,ans=,tot=;

 int f[][maxn]={};

 bool vis[maxn]={};

 queue< int >q;

 void init(int x,int y,int v){

     e[][++tot].y=y;e[][tot].v=v;e[][tot].next=head[][x];head[][x]=tot;

     e[][tot].y=x;e[][tot].v=v;e[][tot].next=head[][y];head[][y]=tot;

 }

 void SPFA(int x,int z){

     for(int i=;i<=n;i++)vis[i]=;

     q.push(x);vis[x]=;dis[z][x]=;

     int y,v,v1;

     while(!q.empty()){

         x=q.front();q.pop();v=dis[z][x];

         for(int i=head[z][x];i;i=e[z][i].next){

             y=e[z][i].y;v1=e[z][i].v;

             if(dis[z][y]>v+v1){

                 dis[z][y]=v+v1;

                 if(!vis[y])q.push(y);

                 vis[y]=;

             }

         }

         vis[x]=;

     }

 }

 bool Topsort(){

     for(int i=;i<=n;i++)d[i]=;

     for(int i=;i<=n;i++){

         for(int j=head[][i];j;j=e[][j].next){

             if(e[][j].v+dis[][i]==dis[][e[][j].y])d[e[][j].y]++;//按照最短路连边

         }

     }cnt=;

     for(int i=;i<=n;i++)if(!d[i])zz[++cnt]=i;

     for(int i=;i<=cnt;i++){

         for(int j=head[][zz[i]];j;j=e[][j].next){

             if(e[][j].v+dis[][zz[i]]==dis[][e[][j].y]){

                 d[e[][j].y]--;

                 if(!d[e[][j].y])zz[++cnt]=e[][j].y;

             }

         }

     }

     for(int j=;j<=n;j++){//如果有0边构成的环，那么这个环一定到最后也有d

         if(d[j]&&dis[][j]+dis[][j]<=k+dis[][n])return ;//如果环在合法路上就不用dp了有无数种方案

     }return ;

 }

 void DP(){

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

         for(int j=;j<=n;j++)f[i][j]=;

     ans=;f[][]=;

     int y,v,x;

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

         for(int j=;j<=cnt;j++){

             x=zz[j];if(dis[][x]==mx)continue;

             for(int w=head[][x];w;w=e[][w].next){

                 y=e[][w].y;v=e[][w].v;

                 if(dis[][x]+v==dis[][y])f[i][y]=(f[i][y]+f[i][x])%p;//用拓扑序给f[k][i]汇总一下

             }

         }

         for(int j=;j<=n;j++){//f[k][x]往下延伸

             x=j;if(dis[][x]==mx)continue;

             for(int w=head[][x];w;w=e[][w].next){

                 y=e[][w].y;v=e[][w].v;

                 if(dis[][x]+v!=dis[][y]){

                     if(i+dis[][x]+v-dis[][y]<=k)

                         f[i+dis[][x]+v-dis[][y]][y]=(f[i+dis[][x]+v-dis[][y]][y]+f[i][x])%p;

                 }

             }

         }ans=(ans+f[i][n])%p;

     }

 }

 int main(){

     //freopen("now.in","r",stdin);

     int T;scanf("%d",&T);mx=(int)1e8;

     while(T-->){

         scanf("%d%d%d%d",&n,&m,&k,&p);

         for(int i=;i<=n;i++)dis[][i]=dis[][i]=mx;

         for(int i=;i<=n;i++)head[][i]=head[][i]=;tot=;

         int x,y,v;

         for(int i=;i<=m;i++){

             scanf("%d%d%d",&x,&y,&v);init(x,y,v);

         }

         SPFA(,);SPFA(n,);//cout<<dis[1][1]<<dis[0][n]<<endl;

         if(dis[][]==mx)printf("0\n");

         else{

             if(Topsort()){

                 printf("-1\n");

             }

             else{

                 DP();

                 printf("%d\n",ans);

             }

         }

     }

     return ;

 }