NOIP2017 逛公园 算是NOIP前补题计划吧
相关题目:逛公园

逛公园

时间限制:3000ms空间限制:512MB

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

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

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

策策同学想知道总共有多少条满足条件的路线,你能帮帮它吗?

为避免输出过大,答案对PP取模。

如果有无穷多条合法的路线,请输出1-1

输入输出格式 输入格式: 第一行包含一个整数 TT, 代表数据组数。

接下来TT组数据,对于每组数据: 第一行包含四个整数 N,M,K,PN,M,K,P,每两个整数之间用一个空格隔开。

接下来MM行,每行三个整数ai,bi,cia_i,b_i,c_i,代表编号为ai,bia_i,b_i的点之间有一条权值为 cic_i的有向边,每两个整数之间用一个空格隔开。

输出格式: 输出文件包含 TT 行,每行一个整数代表答案。

输入输出样例

输入样例:

2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0

输出样例:

3
-1

说明

【样例解释1】

对于第一组数据,最短路为 33 33 条合法路径。

【测试数据与约定】

对于不同的测试点,我们约定各种参数的规模不会超过如下

测试点编号 TT NN MM KK 是否有0边
11 55 55 1010 00
22 55 10001000 20002000 00
33 55 10001000 20002000 5050
44 55 10001000 20002000 5050
55 55 10001000 20002000 5050
66 55 10001000 20002000 5050
77 55 100000100000 200000200000 00
88 33 100000100000 200000200000 5050
99 33 100000100000 200000200000 5050
1010 33 100000100000 200000200000 5050

对于 100%的数据, 1P109,1ai,biN,0ci10001 \le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 1000

数据保证:至少存在一条合法的路线。

Solution

容易想到先求出最短路,然后用 dp[u][z] 表示到达结点 uu 比最短路长 zz 的方案数,但是转移的时候有点麻烦。我们可以考虑搜索。

我们可以从点 11 开始搜索,如果当前多出的长度 >k>k 直接返回。如果当前结点为 nn 时,不返回而是方案数++,因为 nn 可能在环上。前驱点的方案更新只需要回溯的时候更新一下就好了。

对于有 00 边的情况,假设在 一条合法路径上存在 00 环就一定有无穷多的方案数。我们考虑如何找 00 环。注意到 dfs 时会一直在 00 环上循环,故一个点的在栈中的出现次数超过 kk 次,那么它就处在环上,统计一下栈中每个数的个数即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
#define _ 0
#define pii pair<int,int>
#define fi first
#define se second
template <class T>inline void read(T &x) {
x=0; int f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
x*=f;
}
int cnt,nxt[200005],h[100005],to[200005],w[200005];
int n, m, k, p, b, f[100005][51];
priority_queue<pii,vector<pii>,greater<pii> > q;
int dis[100005], vis[100005], tim[100005];
inline void add(int &x) {if(x>=p)x-=p;}
void clear() {
b=cnt=0;memset(h,0,sizeof h);memset(f,-1,sizeof f);memset(tim,0,sizeof tim);
memset(vis,0,sizeof vis);memset(dis,0x7f,sizeof dis);dis[1]=0;
}

void Dijkstra() {
q.push(make_pair(0,1));
while(!q.empty()) {
pii u=q.top(); q.pop();
if(vis[u.se]) continue;
vis[u.se] = 1;
for(int i=h[u.se];i;i=nxt[i]) {
int v = to[i];
if(dis[v] > dis[u.se]+w[i]) {
dis[v] = dis[u.se]+w[i];
q.push(make_pair(dis[v], v));
}
}
}
}

int dfs(int u, int k) {
if(k<0) return 0;
if(f[u][k]!=-1) return f[u][k];
int r=(u==n);
if(++tim[u]>50) return -(b=1);
for(int i=h[u];i&&!b;i=nxt[i])
add(r+=dfs(to[i],k-(w[i]-(dis[to[i]]-dis[u]))));
--tim[u];
return b?-1:f[u][k]=r;
}

int main() {
int T;
read(T);
while(T--) {
clear();
read(n), read(m), read(k), read(p);
static int u, v, W;
while(m--) {
read(u), read(v), read(W);
nxt[++cnt]=h[u],to[h[u]=cnt]=v,w[cnt]=W;
}
Dijkstra();
printf("%d\n", dfs(1,k));
}
return ~~(0^_^0);
}