AK-dream

逛公园「NOIP2017」

AK-dream

发布于：2019年8月6日
次浏览

大家好我叫蒟蒻，这是我的第一篇信竞题解blog

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

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

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

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

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

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

【输入格式】
第一行包含一个整数$T$, 代表数据组数。

接下来$T$组数据，对于每组数据：

第一行包含四个整数$N,M,K,PN,M,K,P$， 每两个整数之间用一个空格隔开。

接下来$m$行，每行三个整数$a_i,b_i,c_i$， 代表编号为$a_i,b_i$的点之间有一条权值为$c_i$的有向边，每两个整数之间用一个空格隔开。

【输出格式】
输出文件包含$T$行，每行一个整数代表答案。

【思路点拨】
是个人应该都能看出此题是要先求出最短路.jpg

亲测此题SPFA跑的比Dijkstra快
为什么？我人品好
最短路只能求出路径长度，计算路径条数似乎做不到——
然后就gg了
据说NOIP2017 Day1三题都没有DP 作为Day2压轴题 DP是压轴出场
What is DP? Is that Dui Pai?

考虑DP的子状态 肯定有一维是要存储当前的点编号
注意到此题$k \le 50$第二维可以存储当前路径1-i的长度超出了1-i最短路多少
于是$dp[i][j]$就表示$1-i$路径长度为$dis[i]$($1-i$最短路)$+ j$的方案数

对于任意一个$u$, 设它有一条路径连向$v$。
则可以推出$dp[u][l] = \sum dp[v][dis[u]-dis[v]+l-edge(u, v)] (1 \le l \le k)$
然后就可以开始快乐DP了

如何判断$0$环？
dfs的时候记录一下就行了
要记得加记忆化搜索

贴心提示

日常全开$long long$是好习惯 多卡常 出奇迹

【代码实现】

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
#define ri register long long
using namespace std;
typedef long long ll;
	 
ll t, n, m, k, p, ans;
ll head[200005], pre[800005], to[800005], val[800005], len;
ll head2[200005], pre2[800005], to2[800005], val2[800005], len2;
ll dis[200005], dis2[200005], visit[200005][61];




ll dp[200005][61];//又到了我们最喜欢的DP时间 




bool vis[200005], ok;

inline ll read() {
	ll ret = 0, flag = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0') {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') {
		ret = (ret << 1) + (ret << 3) + (ch ^ '0');
		ch = getchar();
	}
	return ret * flag;
} 

inline void write(ll num) {
	if (num > 9) write(num / 10);
	putchar(num % 10 + '0');
}

inline void insert(ll u, ll v, ll w) {
	pre[++len] = head[u]; head[u] = len; 
            to[len] = v; val[len] = w;
}

inline void insert2(ll u, ll v, ll w) {
	pre2[++len2] = head2[u]; head2[u] = len2; 
            to2[len2] = v; val2[len2] = w;
}

inline void add(ll &a, ll b) {            //究极玄学卡常 
	a += b;
	if (a > p) {
		a -= p;
	}
}

inline void SPFA() {
	vis[1] = 1;
	dis[1] = 0;
	queue<ll> q;
	q.push(1);
	while (!q.empty()) {
		ll x = q.front();
		q.pop();
		for (ri i = head[x]; i != 0; i = pre[i]) {
			ll y = to[i];
			if (dis[y] > dis[x] + val[i]) {
				dis[y] = dis[x] + val[i];
				if (!vis[y]) {
					vis[y] = 1;
					q.push(y);
				}
			}
		}
		vis[x] = 0;
	}
}

ll dfs(ll c, ll nowk) {
	if (dp[c][nowk] != -1) return dp[c][nowk];
	visit[c][nowk] = 1;
	dp[c][nowk] = 0;
	for (ri i = head2[c]; i; i = pre2[i]) {
		ll next = dis[c] - dis[to2[i]] + nowk - val2[i];
		
		if (next < 0) continue;
		if (visit[to2[i]][next]) {
			ok = 1;
		}
		add(dp[c][nowk], dfs(to2[i], next));
	}
	visit[c][nowk] = 0;
	return dp[c][nowk];
}

void This_is_a_dp() {
	dp[1][0] = 1;
	for (ri i = 0; i <= k; i++) {
		add(ans, dfs(n, i));
	}
}

int main() {
	t = read();
	while (t--) {
		memset(head, 0, sizeof(head));
		memset(head2, 0, sizeof(head2));
		memset(dp, -1, sizeof(dp));
		memset(visit, 0, sizeof(visit));
		memset(vis, 0, sizeof(vis));
		memset(dis, 0x7f, sizeof(dis));
		ok = 0;
		len = ans = len2 = 0;
		n = read();
		m = read();
		k = read();
		p = read();
		for (ri i = 1; i <= m; i++) {
			ll u, v, w;
			u = read();
			v = read();
			w = read();
			insert(u, v, w);
			insert2(v, u, w);
		}
		SPFA();
		/*DP!*/
		This_is_a_dp();
		dfs(n, k + 1);
		if (ok) {
			puts("-1");
			continue;
		}
		write(ans); puts("");
	}
	return 0;
}

时间复杂度$O((k+x)m)$$(x$为$SPFA$玄学次数$)$

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://akdream.tk/post/fdd8486f.html/

更新于：2020年10月8日

最短路

动态规划

评论