NOIP2017 逛公园 洛谷3953（Day1 T3）

WWX

https://www.luogu.org/problemnew/show/P3953
题目很长，就不贴了
此题值得仔细思考，品味。
在写这题之前，建议先完成路径统计洛谷1068（https://www.luogu.org/problemnew/show/P1608）以及最短路计数洛谷1144（https://www.luogu.org/problemnew/show/P1144）
我们发现k的范围只有50，所以可以考虑用dp来解决这个问题
我们用dp[j]表示到节点i的长度为dis+j的路径条数dis为到节点i的最短距离
然后就可以写出转移方程dp[j]+=dp[k][j-(dis[j]-dis[k]+dis[j])]k为所用可以到达i的节点
在考虑什么时候会有无数条路径，显然是当图存在0环的时候
我们打一个标记在统计时判断一下，就好了
由于不太好推，我们利用记忆化搜索来实现代码

胡雨菲菲

太强了！%%%

WWX

1. # include<algorithm>
   
2. # include<iostream>
   
3. # include<cstring>
   
4. # include<cstdio>
   
5. # include<queue>
   
6. const int  mn  = 100010;
   
7. const int  maxn  =  200010;
   
8. inline int read()
   
9. {
   
10.     int x=0;
    
11.     char ch=getchar();
    
12.     while(ch<'0'||ch>'9') ch=getchar();
    
13.     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    
14.     return x;
    
15. }
    
16. using namespace std;
    
17. int t,n,m,K,p,ans,edge_max;
    
18. int dp[mn][51],mark[mn][51];
    
19. int dis[mn],head1[mn],head2[mn];
    
20. bool flag;
    
21. bool vis[mn];
    
22. queue<int> q;
    
23. struct edge{int to,dis,next;}e1[maxn],e2[maxn];
    
24. void add(int x,int y,int z)
    
25. {
    
26.     e1[++edge_max].to=y;
    
27.     e1[edge_max].dis=z;
    
28.     e1[edge_max].next=head1[x];
    
29.     head1[x]=edge_max;
    
30.     e2[edge_max].to=x;
    
31.     e2[edge_max].dis=z;
    
32.     e2[edge_max].next=head2[y];
    
33.     head2[y]=edge_max;
    
34. }
    
35. void pre()
    
36. {
    
37.     dis[1]=0;
    
38.     q.push(1);
    
39.     while(!q.empty())
    
40.     {
    
41.         int u=q.front();
    
42.         q.pop();
    
43.         vis[u]=0;
    
44.         for(int i=head1[u];i;i=e1[i].next)
    
45.         {
    
46.             if(dis[u]+e1[i].dis<dis[e1[i].to])
    
47.             {
    
48.                 dis[e1[i].to]=dis[u]+e1[i].dis;
    
49.                 if(!vis[e1[i].to])
    
50.                 {
    
51.                     vis[e1[i].to]=1;
    
52.                     q.push(e1[i].to);
    
53.                 }
    
54.             }
    
55.         }
    
56.     }
    
57. }
    
58. int dfs(int x,int k)
    
59. {
    
60.     if(flag)
    
61.         return 0;
    
62.     if(mark[x][k]==1)//如果有0环，路径则有无数条
    
63.     {
    
64.         flag=true;
    
65.         return 0;
    
66.     }
    
67.     if(mark[x][k]==2)
    
68.         return dp[x][k];
    
69.     mark[x][k]=1;
    
70.     for(int i=head2[x];i;i=e2[i].next)
    
71.     {
    
72.         int u=e2[i].to,len=e2[i].dis;
    
73.         if(dis[u]+len>dis[x]+k)
    
74.             continue;
    
75.         dp[x][k]+=dfs(u,k-(dis[u]+len-dis[x]));
    
76.         if(flag) return 0;
    
77.         dp[x][k]%=p;
    
78.     }
    
79.     mark[x][k]=2;
    
80.     return dp[x][k];
    
81. }
    
82. int main()
    
83. {
    
84.     int x,y,z;
    
85.     t=read();
    
86.     while(t--)
    
87.     {
    
88.         ans=0;
    
89.         flag=false;
    
90.         memset(dis,0xf,sizeof(dis));
    
91.         memset(head1,0,sizeof(head1));
    
92.         memset(head2,0,sizeof(head2));
    
93.         memset(dp,0,sizeof(dp));
    
94.         memset(mark,0,sizeof(mark));
    
95.         edge_max=0;
    
96.         n=read(),m=read(),K=read(),p=read();
    
97.         for(int i=1;i<=m;i++)
    
98.         {
    
99.             x=read(),y=read(),z=read();
    
100.             add(x,y,z);
     
101.         }
     
102.         pre();
     
103.         dp[1][0]=1;
     
104.         for(int i=0;i<=K;i++)
     
105.         {
     
106.             ans+=dfs(n,i);
     
107.             //printf("%d\n",ans);
     
108.             ans%=p;
     
109.         }
     
110.         if(flag)
     
111.             puts("-1");
     
112.         else printf("%d\n",ans);
     
113.     }
     
114.     return 0;
     
115. }

复制代码