【NOIP2017】逛公园（最短路图，拓扑排序，计数DP）

题意：

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

策策每天都会去逛公园，他总是从 1 号点进去，从 N 号点出来。

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

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

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

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

n<=1e5，m<=2e5，K<=50,1≤P≤1e9，0≤ci≤1000。

思路：因为K很小，建立以1为源点的最短路图，在最短路图上进行DP计数

dp[i][j]表示当前在点i，比最短路线多走j时间的方案数

在1到N的最短路上可能有环，这样会出现-1的情况，同时还有边长为0的存在，这两个问题都可以使用拓扑排序解决

对于-1拓扑排序后直接判断

对于边长为0按照拓扑序进行转移

 #include<cstdio>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<map>

 #include<set>

 #include<queue>

 #include<vector>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef vector<int> VI;

 #define fi first

 #define se second

 #define MP make_pair

 #define N   110000

 #define M   210000

 #define eps 1e-8

 #define pi acos(-1)

 priority_queue<pair<int,int> > q;

 int dp[N][],head[M],vet[M],nxt[M],len[M],head2[M],vet2[M],nxt2[M],len2[M],

     dis[N],dis2[N],vis[N],p[N],d[N],tot,tot2;

 void add(int a,int b,int c)

 {

     nxt[++tot]=head[a];

     vet[tot]=b;

     len[tot]=c;

     head[a]=tot;

 }

 void add2(int a,int b,int c)

 {

     nxt2[++tot2]=head2[a];

     vet2[tot2]=b;

     len2[tot2]=c;

     head2[a]=tot2;

 }

 int main()

 {

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

   //  freopen("uoj331.out","w",stdout);

     int cas;

     scanf("%d",&cas);

     for(int v1=;v1<=cas;v1++)

     {

         int n,m,K,MOD;

         scanf("%d%d%d%d",&n,&m,&K,&MOD);

         tot=tot2=;

         memset(head,,sizeof(head));

         memset(head2,,sizeof(head2));

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

         {

             int x,y,z;

             scanf("%d%d%d",&x,&y,&z);

             add(x,y,z);

             add2(y,x,z);

         }

         //printf("readend\n");

         memset(vis,,sizeof(vis));

            memset(dis,0x3f,sizeof(dis));

         memset(d,,sizeof(d));

         q.push(MP(,)); dis[]=;

         while(!q.empty())

         {

             int u=q.top().se;

             q.pop();

             if(vis[u]) continue;

             vis[u]=;

             int e=head[u];

             while(e)

             {

                 int v=vet[e];

                 if(dis[u]+len[e]<dis[v])

                 {

                     dis[v]=dis[u]+len[e];

                     q.push(MP(-dis[v],v));

                 }

                 e=nxt[e];

             }

         }

         //printf("dijk1end\n");

         memset(vis,,sizeof(vis));

         memset(dis2,0x3f,sizeof(dis2));

         q.push(MP(,n)); dis2[n]=;

         while(!q.empty())

         {

             int u=q.top().se;

             q.pop();

             if(vis[u]) continue;

             vis[u]=;

             int e=head2[u];

             while(e)

             {

                 int v=vet2[e];

                 if(dis2[u]+len2[e]<dis2[v])

                 {

                     dis2[v]=dis2[u]+len2[e];

                     q.push(MP(-dis2[v],v));

                 }

                 e=nxt2[e];

             }

         }

         //printf("dijk2end\n");

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

         {

             int e=head[i];

             while(e)

             {

                 int v=vet[e];

                 if(dis[i]+len[e]==dis[v]) d[v]++;

                 e=nxt[e];

             }

         }

         tot=;

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

          if(!d[i]) p[++tot]=i;

         //printf("%d\n",tot);

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

         {

             int u=p[i];

             int e=head[u];

             while(e)

             {

                 int v=vet[e];

                 if(dis[u]+len[e]==dis[v])

                 {

                     d[v]--;

                     if(!d[v]) p[++tot]=v;

                 }

                 e=nxt[e];

             }

         }

         //printf("topoend\n");

         int flag=;

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

          if(d[i]&&dis[i]+dis2[i]<=dis[n]+K)

          {

              printf("-1\n");

              flag=;

              break;

          }

         if(!flag) continue;

         memset(dp,,sizeof(dp));

         dp[][]=;

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

         {

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

             {

                 int u=p[i];

                 int e=head[u];

                 while(e)

                 {

                     int v=vet[e];

                     if(dis[u]+len[e]==dis[v]) dp[v][k]=(dp[v][k]+dp[u][k])%MOD;

                     e=nxt[e];

                 }

             }

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

             {

                 int e=head[i];

                 while(e)

                 {

                     int v=vet[e];

                     int t=k+dis[i]+len[e]-dis[v];

                      if(dis[i]+len[e]!=dis[v]&&t<=K) dp[v][t]=(dp[v][t]+dp[i][k])%MOD;

                     e=nxt[e];

                 }

             }

         }

         ll ans=;

         for(int i=;i<=K;i++) ans=(ans+dp[n][i])%MOD;

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

     }

     return ;

 }

巴特西

【NOIP2017】逛公园（最短路图，拓扑排序，计数DP）

最新文章

热门文章