一张nn个点mm条边的简单有向图,求dis(1,n)≤MinDis(1,n)+Kdis(1,n) \le MinDis(1,n) + K的路径数

Luogu P3953

Constraints

N≤105,M≤2∗105,K≤50N \le 10^5, M\le 2 * 10^5, K\le 50,存在为0的边

1≤P≤109,1≤ai,bi≤N,0≤ci≤10001 \le P \le 10^9,1 \le a_i,b_i \le N ,0 \le c_i \le 1000

Solution

很显然是一个关于K的Dp

先预处理出MinDis(x,n)MinDis(x,n)表示xx到nn的最短路

设Dp[x][k]Dp[x][k]表示到第xx个点,dis(x,n)≤MinDis(x,n)+kdis(x,n)\le MinDis(x,n)+k的方案数,答案就是Dp[1][K]Dp[1][K]

对于一条边(x,y,w)(x, y, w), 它所消耗的kk为MinDis(y,n)−MinDis(x,n)+wMinDis(y,n) - MinDis(x,n) + w

如果MinDis(y,n)−MinDis(x,n)+w≤kMinDis(y,n) - MinDis(x,n) + w \le k

那么Dp[x][k]+=Dp[y][k−(MinDis(y,n)−MinDis(x,n)+w)]Dp[x][k]+= Dp[y][k - (MinDis(y,n) - MinDis(x,n) + w)]

直接记忆化搜索即可,对于0环只需要用一个栈记录一下:如果当前搜索的(x,k)(x,k)还在栈中就返回-1

这样做的话因为每个状态最多只会遍历到一次（或者这样理解：在转移的时候k在不断减小），所以时间复杂度是能保证的

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
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
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
inline int read ()
{
	int sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

const int Maxn = 100000 + 100, Maxm = 200000 + 100, Maxk = 50 + 10, inf = 0x3f3f3f3f;

int N, M, K, Mod, e, Begin[Maxn], To[Maxm], Next[Maxm], W[Maxm];
int Dp[Maxn][Maxk], In[Maxn][Maxk];

inline void add_edge (int x, int y, int z) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; }

inline void Init() 
{ 
	e = 0; 
	memset(Begin, 0, sizeof Begin); 
	memset(Dp, 0, sizeof Dp); 
	memset(In, 0, sizeof In); 
}

int Dis[Maxn], Vis[Maxn];

namespace Dijkstra
{
	int e1, Begin1[Maxn], To1[Maxm], Next1[Maxm], W1[Maxm];
	struct node
	{
		int a, b;
		bool operator < (const node &x) const { return x.b < b; }
	};

	inline void init() { e1 = 0; memset(Begin1, 0, sizeof Begin1); }

	inline void add_edge (int x, int y, int z) { To1[++e1] = y; Next1[e1] = Begin1[x]; Begin1[x] = e1; W1[e1] = z; }

	inline void work (int S)
	{
		static priority_queue <node> Q;
		for (int i = 1; i <= N; ++i) Dis[i] = inf, Vis[i] = 0;
		Dis[S] = 0; Q.push((node){S, 0});
		while (!Q.empty())
		{
			int x = Q.top().a; Q.pop();
			if (Vis[x]) continue;
			Vis[x] = 1;
			for (int i = Begin1[x]; i; i = Next1[i])
			{
				int y = To1[i];
				if (Chkmin(Dis[y], Dis[x] + W[i])) Q.push((node){y, Dis[y]});
			}
		}
	}
}

inline int dfs (int x, int k)
{
//	cout<<x<<" "<<k<<endl;
	if (In[x][k]) return -1;
	if (Dp[x][k]) return Dp[x][k];
	In[x][k] = 1;
	if (x == N) Dp[x][k] = 1;
	for (int i = Begin[x]; i; i = Next[i])
	{
		int y = To[i];
		int tmp = Dis[y] - Dis[x] + W[i];
		if (tmp <= k)
		{
			int sum = dfs(y, k - tmp);
			if (sum == -1) return Dp[x][k] = -1;
			(Dp[x][k] += sum) %= Mod;
		}
	}
	In[x][k] = 0;
	return Dp[x][k];
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("park.in", "r", stdin);
	freopen("park.out", "w", stdout);
#endif
	int Test = read();
	while (Test--)
	{
		Init();
		Dijkstra :: init();
		N = read(), M = read(), K = read(), Mod = read();
		for (int i = 1; i <= M; ++i)
		{
			int x = read(), y = read(), z = read();
			add_edge (x, y, z);
			Dijkstra :: add_edge (y, x, z);
		}
		Dijkstra :: work (N);
//		for (int i = 1; i <= N; ++i) cout<<Dis[i]<<" ";
//		cout<<endl;
		printf("%d\n", dfs(1, K));
	}
	return 0;
}