NOIP2017 D1T3逛公园

DP+最短路
两遍最短路判零环
DP转移f[i][j] 到点i的距离比最短路多j时的方案数
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=400005;
  4 struct node
  5 {
  6     int to,nex,w;
  7 }e[N],z[N];
  8 int cnt,cnt1,head[100005],head2[100005];
  9 int add(int x,int y,int w)
 10 {
 11     e[++cnt1].to=y;e[cnt1].w=w;e[cnt1].nex=head[x];head[x]=cnt1;
 12     z[++cnt].to=x;z[cnt].w=w;z[cnt].nex=head2[y];head2[y]=cnt;
 13 }
 14 int f[100005][51];
 15 int d1[100005],d2[100005],d[100005],qq[N<<1];
 16 bool v[100005];int n,m,k,p;
 17 void update(int &a,int b)
 18 {
 19     a=(a+b)%p;
 20 }
 21 queue<int>q;
 22 void work()
 23 {
 24     scanf("%d%d%d%d",&n,&m,&k,&p);cnt=0,cnt1=0;
 25     memset(head,0,sizeof(head));
 26     memset(head2,0,sizeof(head2));
 27     for(int i=1;i<=m;++i)
 28     {
 29         int x,y,w;
 30         scanf("%d%d%d",&x,&y,&w);
 31         add(x,y,w);
 32     }
 33     memset(v,0,sizeof(v));memset(d1,0x3f,sizeof(d1));
 34     q.push(1);d1[1]=0;v[1]=1;
 35     while(!q.empty())
 36     {
 37         int x=q.front();q.pop();v[x]=0;
 38         for(int i=head[x];i;i=e[i].nex)
 39         {
 40             int y=e[i].to;
 41             if(d1[y]>d1[x]+e[i].w)
 42             {
 43                 d1[y]=d1[x]+e[i].w;
 44                 if(!v[y])
 45                 {
 46                     q.push(y);v[y]=1;
 47                 }
 48             }
 49         }
 50     }
 51     memset(v,0,sizeof(v));memset(d2,0x3f,sizeof(d2));
 52     q.push(n);d2[n]=0;v[n]=1;
 53     while(!q.empty())
 54     {
 55         int x=q.front();q.pop();v[x]=0;
 56         for(int i=head2[x];i;i=z[i].nex)
 57         {
 58             int y=z[i].to;
 59             if(d2[y]>d2[x]+z[i].w)
 60             {
 61                 d2[y]=d2[x]+z[i].w;
 62                 if(!v[y])
 63                 {
 64                     q.push(y);v[y]=1;
 65                 }
 66             }
 67         }
 68     }
 69     
 70     int top=0;memset(d,0,sizeof(d));
 71     for(int i=1;i<=n;++i)
 72     for(int j=head[i];j;j=e[j].nex)
 73     {
 74         if(d1[i]+e[j].w==d1[e[j].to])d[e[j].to]++;
 75     }
 76     for(int i=1;i<=n;++i)if(!d[i])qq[++top]=i;
 77     for(int i=1;i<=top;++i)
 78     {
 79         int x=qq[i];
 80         for(int j=head[x];j;j=e[j].nex)
 81         if(d1[x]+e[j].w==d1[e[j].to])
 82         {
 83             int y=e[j].to;
 84             d[y]--;
 85             if(d[y]==0)qq[++top]=y;
 86         }
 87     }
 88     for(int i=1;i<=n;++i)
 89     if(d[i]&&d1[i]+d2[i]<=d1[n]+k)
 90     {
 91         puts("-1");return;
 92     }
 93     int ans=0;
 94     memset(f,0,sizeof(f));
 95     f[1][0]=1;
 96     for(int i=0;i<=k;++i)
 97     {
 98         for(int j=1;j<=top;++j)
 99         for(int u=head[qq[j]];u;u=e[u].nex)
100         {
101             if(d1[qq[j]]+e[u].w==d1[e[u].to])
102             update(f[e[u].to][i],f[qq[j]][i]);
103         }
104         
105         for(int j=1;j<=n;++j)
106         for(int u=head[j];u;u=e[u].nex)
107         {
108             if(d1[j]+e[u].w!=d1[e[u].to]&&i+d1[j]-d1[e[u].to]+e[u].w<=k)
109             update(f[e[u].to][i+d1[j]-d1[e[u].to]+e[u].w],f[j][i]);
110         }
111     }
112     for(int i=0;i<=k;++i)
113     update(ans,f[n][i]);
114     printf("%d\n",ans);
115     return ;
116 }
117 int main()
118 {
119     int t;scanf("%d",&t);
120     while(t--)
121     {
122         work();
123     }
124     return 0;
125 }