U
p
d
Upd
Upd：
2022.11.28
2022.11.28
2022.11.28 完成
八中OJ鏈接
我們還是先觀察數(shù)據(jù)范圍：
1
≤
n
,
m
≤
500
1 \leq n,m \leq 500
1≤n,m≤500,那么就只能用廣度優(yōu)先搜索了。
個(gè)人認(rèn)為這道題出得不好，因?yàn)榘凑漳壳暗淖顑?yōu)解，時(shí)間復(fù)雜度應(yīng)該為
O
(
n
2
m
2
)
O(n^2m^2)
O(n2m2) 的，應(yīng)該是過不掉的，但為什么在
150
m
s
150ms
150ms 內(nèi)就過掉了呢？原因有二：一是數(shù)據(jù)太水，僅有一組極限數(shù)據(jù)并且 ‘#’ 符號(hào)少得可憐。二是如果每一次
b
f
s
bfs
bfs 不用
O
(
n
m
)
O(nm)
O(nm) 的時(shí)間初始化，其實(shí)真正的時(shí)間復(fù)雜度是遠(yuǎn)遠(yuǎn)小于
O
(
n
2
m
2
)
O(n^2m^2)
O(n2m2) 的。
我們先來想一想最暴力的做法，枚舉兩個(gè)城市，再用
O
(
n
m
)
O(nm)
O(nm) 求其最短距離，這樣做是
O
(
n
3
m
3
)
O(n^3m^3)
O(n3m3) 的，絕對(duì)會(huì)原地起飛。
現(xiàn)在，來說說這道題的正確做法——染色法，即將每個(gè)城市用
d
f
s
dfs
dfs 染色后去求解。如果每個(gè)城市只有一個(gè) #，那么，這個(gè)問題就是一個(gè)很裸的
B
F
S
BFS
BFS 問題。但是，現(xiàn)在的問題就是，要如何
做，才能夠求得一片城市與另一片城市的最短距離？其實(shí)，每一次
b
f
s
bfs
bfs 最壞會(huì)遍歷整個(gè)地圖，并且我們只是求其最小距離，所以，我們可以將某一個(gè)城市內(nèi)的所有 # 全都作為我們搜索的起點(diǎn)，然后計(jì)算從這些起點(diǎn)當(dāng)中，走到另一個(gè) # 的最短距離是多少（
B
F
S
BFS
BFS），因?yàn)槲覀冎恍枰业阶钚【嚯x，并不需要知道究竟是哪個(gè)城市到了另外哪個(gè)城市，因此，我們?cè)谂?
B
F
S
BFS
BFS 之前，找到當(dāng)前我們找的這個(gè)城市有哪些 #，將同一個(gè)城市內(nèi)的所有#都
p
u
s
h
push
push 進(jìn)我們的隊(duì)列當(dāng)中，然后，再跑一個(gè)
B
F
S
BFS
BFS，找到這個(gè)城市能走到的離它最近的城市的距離，最后取最小的那個(gè)答案即可。
A
C
AC
AC
C
o
d
e
:
Code:
Code:
重慶分公司
重慶分公司
#includeusing namespace std;
const int N = 5e2 + 5, INF = 0x3f3f3f3f;
const int zx[4] = {-1, 0, 1, 0}, zy[4] = {0, 1, 0, -1};
int n, m, ans = INF;
char c[N][N];
bool vis[N][N];
struct node {int x, y, step;
};
queueq;
bool in(int x, int y) {return x >= 1 && x<= n && y >= 1 && y<= m;
}
void dfs(int x, int y) {c[x][y] = 'A';
q.push((node){x, y, 0});
for(int i = 0;i< 4;i++) {int dx = x + zx[i], dy = y + zy[i];
if(in(dx, dy) && c[dx][dy] == '#') dfs(dx, dy);
}
}
void bfs() {for (int i = 1;i<= n;i++)
for (int j = 1;j<= m;j++)
vis[i][j] = 0;
while(!q.empty()) {node p = q.front();
q.pop();
if(c[p.x][p.y] == '#') { while(!q.empty()) q.pop();
ans = min(ans, p.step);
return ;
}
for(int i = 0;i< 4; ++i) { int dx = p.x + zx[i], dy = p.y + zy[i];
if(in(dx, dy) && !vis[dx][dy] && c[dx][dy] != 'A') { vis[dx][dy] = 1;
q.push((node){dx, dy, p.step + 1});
}
}
}
}
int main() {scanf("%d%d", &n, &m);
for(int i = 1;i<= n;i++) scanf("%s", c[i] + 1);
for(int i = 1;i<= n;i++)
for(int j = 1;j<= m;j++)
if(c[i][j] == '#') { dfs(i, j);
bfs();
}
printf("%d", ans);
return 0;
}
U
p
d
Upd
Upd：
2022.11.26
2022.11.26
2022.11.26 完成
洛谷鏈接 八中OJ鏈接
看到數(shù)據(jù)范圍
1
0
10
≤
L
≤
R
≤
1
0
11
10^{10} \leq L \leq R \leq 10^{11}
1010≤L≤R≤1011 并且是統(tǒng)計(jì)
[
L
,
R
]
[L,R]
[L,R] 內(nèi)有滿足條件的號(hào)碼數(shù)量，很容易想到數(shù)位
D
P
DP
DP。
其實(shí)，數(shù)位
D
P
DP
DP 也是一個(gè)很模板化的東西。對(duì)其總結(jié)如下：
dfs(數(shù)的最后若干位,各種限制條件,當(dāng)前第幾位)
if 最后一位
return 各種限制條件下的返回值
局部變量 ct = 當(dāng)前位的數(shù)字
局部變量 sum = 0;
for i = 0 to ct - 1
sum += 當(dāng)前位取i時(shí)一定無無限制的合法狀態(tài)數(shù)
sum += 當(dāng)前位取i時(shí)滿足當(dāng)前限制的合法狀態(tài)數(shù)
根據(jù)ct更新限制條件 不再滿足則 return sum
return sum + dfs(當(dāng)前位后的若干位,更新后的限制條件,下一位)
slv(當(dāng)前數(shù))
if (只有一位) return 對(duì)應(yīng)的貢獻(xiàn)
局部變量 ct;
for ct = 可能最高位 to 1
if 當(dāng)前位有數(shù)字 break
局部變量 nw = 當(dāng)前位數(shù)字
局部變量 sum = 0
for i = 1 to nw - 1
sum += 當(dāng)前位取i后合法情況任意取的貢獻(xiàn)
for i = 1 to ct-1
for j = 1 to 9
sum += 第i位取j后合法情況任意取的貢獻(xiàn)
sum += dfs(去掉第一位后的若干位,限制條件,第二位)
return sum
main
預(yù)處理當(dāng)前位取i的各種條件各種限制的貢獻(xiàn)
讀入 L R
--L
輸出 slv(R)-slv(L)
return 0而在這道題中，我們就可以很容易的套模板，定義六維的
D
P
DP
DP 去記憶化
d
f
s
dfs
dfs,即
d
p
[
第
i
位
]
[
填
j
]
[
目
前
連
續(xù)
L
]
[
是
否
有
4
]
[
是
否
有
8
]
[
是
否
有
至
少
3
位
連
續(xù)
數(shù)
字
]
dp[第i位][填j][目前連續(xù)L][是否有4][是否有8][是否有至少3位連續(xù)數(shù)字]
dp[第i位][填j][目前連續(xù)L][是否有4][是否有8][是否有至少3位連續(xù)數(shù)字]。
然后按照板子按部就班的做便能
A
C
AC
AC.
A
C
AC
AC
C
o
d
e
Code
Code:
#includeusing namespace std;
#define int long long
const int N = 20;
int x, y, num[N], dp[N][N][N][2][2][2];
int dfs(int pos, int pre1, int pre2, bool limit, bool zero, bool e, bool f, bool ok) {if (e && f) return 0;
if (!pos) return ok;
if (!limit && !zero && dp[pos][pre1][pre2][e][f][ok]) return dp[pos][pre1][pre2][e][f][ok];
int mxd = limit ? num[pos] : 9;
int ans = 0;
for (int i = 0; i<= mxd;i++)
ans += dfs(pos - 1, (zero && !i) ? -1 : i, zero ? -1 : pre1, limit && i == mxd, zero && !i, e || i == 8, f || i == 4, ok || ((!zero && i == pre1 && i == pre2)));
if (!limit && !zero) dp[pos][pre1][pre2][e][f][ok] = ans;
return ans;
}
int solve(int x) {int len = 0;
while (x) num[++len] = x % 10, x /= 10;
return dfs(len, -1, -1, 1, 1, 0, 0, 0);
}
signed main() {scanf("%lld%lld", &x, &y);
printf("%lld", solve(y) - solve(x - 1));
return 0;
}
U
p
d
Upd
Upd：
2022.11.26
2022.11.26
2022.11.26 完成
洛谷鏈接
解題思路：由數(shù)據(jù)范圍
1
≤
x
≤
1
0
9
1 \leq x \leq 10^9
1≤x≤109 可得，這是一道思維題。
思維題，其實(shí)無非分為以下四種：拼湊、歸納、分類、數(shù)論。
而這一題，題中沒有復(fù)雜的數(shù)學(xué)公式，便可以從拼湊角度出發(fā)。
隨便列舉出一些數(shù)字：
122
=
111
?
1
+
11
?
1
122 = 111 * 1 + 11 * 1
122=111?1+11?1,
233
?
111
?
2
+
11
?
1
233 - 111 * 2 + 11 * 1
233?111?2+11?1
發(fā)現(xiàn)，似乎三位數(shù)可以由
11
11
11 和
111
111
111 拼湊，那么更高位數(shù)字呢？。
我們又可以發(fā)現(xiàn)：
11
?
>
11
11 ->11
11?>11
111
?
>
111
111 ->111
111?>111
1111
?
>
11
×
100
+
11
1111 ->11 \times 100 + 11
1111?>11×100+11
11111
?
>
11
×
1000
+
111
11111 ->11 \times 1000 + 111
11111?>11×1000+111
111111
?
>
1111
×
10
+
11
?
>
11
×
1000
+
1111
111111 ->1111 \times 10 + 11 ->11 \times 1000 + 1111
111111?>1111×10+11?>11×1000+1111
又因?yàn)?
111
=
11
×
10
+
1
111 = 11 \times 10 + 1
111=11×10+1
所以
11
x
+
111
y
=
11
（
x
+
10
y
）
+
1
11x + 111y = 11（x + 10y）+1
11x+111y=11（x+10y）+1
此時(shí)，我們就可以求解出
x
、
y
x、y
x、y 的值。
我們還可以發(fā)現(xiàn)這些數(shù)的一個(gè)美好特征：永遠(yuǎn)可以將一個(gè)非常大的數(shù)字消到三位數(shù)以下，也就說我們可以分段打表（有人
A
C
AC
AC 過）求出
x
%
11
×
111
x \% 11 \times 111
x%11×111 后判斷是否小于
x
x
x 即可。
A
C
AC
AC
C
o
d
e
Code
Code:
#includeusing namespace std;
#define int long long
int T, x;
signed main() {scanf("%lld", &T);
while(T--) {scanf("%lld", &x);
if (x % 11 * 111<= x) puts("YES");
else puts("NO");
}
return 0;
}
//num = 11 * x + 111 * y
//num = 11 * (x + 10 * y) + y
U
p
d
Upd
Upd：
2022.11.26
2022.11.26
2022.11.26 完成
八中OJ鏈接 洛谷鏈接
可以觀察數(shù)據(jù)范圍
1
≤
a
i
≤
20
1 \leq a_i \leq 20
1≤ai?≤20,可以用狀壓
D
P
DP
DP 求解。
細(xì)看題目，便發(fā)現(xiàn)有這樣一個(gè)性質(zhì)：如果交換相鄰的兩數(shù)，其他所有數(shù)字的相對(duì)位置是不變的。（其實(shí)，也可以根據(jù)逆序?qū)Φ囊粋€(gè)引理得出：將一個(gè)序列排序最少交換相鄰元素的次數(shù)等于該序列的逆序?qū)?shù)。）
推論：在交換的時(shí)候我們就可以分開考慮每一種數(shù)字。
例如:
1
1
1
1
1
1
3
3
3
2
2
2
4
4
4 中,我們發(fā)現(xiàn)交換下標(biāo)為
1
1
1 和
2
2
2 的數(shù)字，其實(shí)序列并沒有改變，而顏色只有
20
20
20 種,也就是相鄰的同種顏色不考慮交換。
于是，我們可以來狀壓顏色的種類。
D
P
DP
DP 的定義如下：定義
d
p
i
dp_i
dpi? 表示表示已選的數(shù)的狀態(tài)集合（注意，每選擇一個(gè)數(shù)，意味著給其賦一個(gè)比之前選的數(shù)都大，比之后選的數(shù)都小的權(quán)值），集合中的數(shù)權(quán)值逆序?qū)Φ淖钚≈怠?br />理解一下：若有一個(gè)序列
1
1
1
2
2
2
1
1
1
3
3
3,
d
p
[
3
]
=
d
p
[
(
011
)
2
]
dp[3] = dp[(011)_2]
dp[3]=dp[(011)2?] (已經(jīng)選擇了
1
1
1 和
2
2
2 兩種數(shù))
=
1
=1
=1.為什么呢？因?yàn)榧热皇乔髾?quán)值逆序?qū)?，即我們可以將它同種類數(shù)字賦上同一個(gè)值，求其值逆序?qū)Φ淖钚≈?。在這里，我們將
1
1
1 賦值為
1
1
1,
2
2
2 賦值為
2
2
2,便會(huì)有一個(gè)逆序?qū)?，就是最小值?br />接著，我們來考慮一下轉(zhuǎn)移方程吧。
d
p
i
dp_i
dpi? 應(yīng)該怎么轉(zhuǎn)移呢？
當(dāng)我們?cè)诟聽顟B(tài)
i
i
i 時(shí)，
i
i
i 以前
d
p
dp
dp 值應(yīng)該是有的，那么，我們可以枚舉顏色的種類，假設(shè)沒有這個(gè)種類的數(shù)字的
d
p
dp
dp 值加上
v
a
l
val
val (
v
a
l
val
val 就是逆序?qū)€(gè)數(shù))，即
d
p
i
=
m
i
n
(
d
p
i
,
d
p
j
+
v
a
l
)
dp_i = min(dp_i,dp_j+val)
dpi?=min(dpi?,dpj?+val)
而這個(gè)
v
a
l
val
val 的值需要用兩重循環(huán)去枚舉，會(huì)
T
T
T！怎么辦？可以用一個(gè)數(shù)組預(yù)處理。用
c
x
y
c_{xy}
cxy? 表示數(shù)列中滿足
i
＜
j
i ＜ j
i＜j 且
a
i
=
x
a_i = x
ai?=x,
a
j
=
y
a_j = y
aj?=y 的
(
i
,
j
)
(i,j)
(i,j) 對(duì)數(shù)。
這樣，這道狀壓
D
P
DP
DP 的題目就可以被解決了，最壞時(shí)間復(fù)雜度為
O
（
4
?
1
0
5
×
20
+
2
20
×
2
0
2
）
O（4*10^5 \times 20 + 2^{20} \times 20^2）
O（4?105×20+220×202） 運(yùn)算次數(shù)約為
4
?
1
0
7
4*10^7
4?107,時(shí)限
4
s
e
c
4 sec
4sec，可以通過。
但是，注意一點(diǎn)，初始化
D
P
DP
DP 時(shí)候，不能只初始化到
1
<
<
m
a
x
n
1<< maxn
1<
#includeusing namespace std;
#define int long long
const int N = 4e5 + 5, M = 25, INF = 0x3f3f3f3f;
int n, maxx, maxn, a[N], cnt[M], c[M][M], dp[(1<< 20) + 5];
signed main() {scanf("%lld", &n);
for (int i = 1;i<= n;i++) scanf("%lld", &a[i]), a[i]--;
maxx = *max_element(a + 1, a + n + 1) + 1, maxn = (1<< maxx) - 1;
for (int i = 1;i<= n;i++) {cnt[a[i]]++;
for (int j = 0;j<= maxx;j++) c[j][a[i]] += cnt[j];
}
for (int i = 1;i<= maxn;i++) dp[i] = INF;
for (int i = 1;i<= maxn;i++)
for (int j = 0;j< maxx;j++)
if (i & (1<< j)) { int val = 0, pre = i - (1<< j);
for (int k = 0;k< maxx;k++) if (pre & (1<< k)) val += c[j][k];
dp[i] = min(dp[i], dp[pre] + val);
}
printf("%lld", dp[maxn]);
return 0;
} A C AC AC C o d e Code Code
#includeusing namespace std;
#define int long long
const int N = 4e5 + 5, M = 25, INF = 0x3f3f3f3f;
int n, maxx, maxn, a[N], cnt[M], c[M][M], dp[(1<< 20) + 5];
signed main() {scanf("%lld", &n);
for (int i = 1;i<= n;i++) scanf("%lld", &a[i]), a[i]--;
maxx = *max_element(a + 1, a + n + 1) + 1, maxn = (1<< maxx) - 1;
for (int i = 1;i<= n;i++) {cnt[a[i]]++;
for (int j = 0;j<= maxx;j++) c[j][a[i]] += cnt[j];
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int i = 1;i<= maxn;i++)
for (int j = 0;j< maxx;j++)
if (i & (1<< j)) { int val = 0, pre = min(i - (1<< j), maxn + 1);
for (int k = 0;k< maxx;k++) if (pre & (1<< k)) val += c[j][k];
dp[i] = min(dp[i], dp[pre] + val);
}
printf("%lld", dp[maxn]);
return 0;
}
U
p
d
Upd
Upd：
2022.11.26
2022.11.26
2022.11.26 完成
八中OJ鏈接 洛谷鏈接
首先，我們要知道
1
?
n
1-n
1?n 的最短路的距離是多少。于是我們可以跑一遍
d
i
j
k
s
t
r
a
dijkstra
dijkstra 來
O
(
n
l
o
g
n
)
O(n log n)
O(nlogn) 求最短距離。
然后我們可以發(fā)現(xiàn)
0
≤
k
≤
50
0 \leq k \leq 50
0≤k≤50 ，于是我們可以在
k
k
k 上面做一個(gè)
D
P
DP
DP。
不難定義出
d
p
u
d
dp_{ud}
dpud? 表示路程為區(qū)間
[
d
i
s
u
,
d
i
s
u
+
d
]
[dis_u, dis_u+d]
[disu?,disu?+d] 以內(nèi)的方案數(shù)（
d
i
s
u
dis_u
disu? 表示到
u
u
u 的最短路)
于是我們可以在每種詢問時(shí)暴力枚舉
k
k
k ，每次用
d
f
s
dfs
dfs 記憶化的方式來計(jì)算
d
p
n
i
dp_{ni}
dpni? 的值，答案即為
d
p
n
i
dp_{ni}
dpni? 之和。
那么
d
f
s
dfs
dfs 應(yīng)該怎么寫呢？
對(duì)于每一個(gè)
d
f
s
dfs
dfs ，我們可以枚舉起點(diǎn)（可以反向建圖，將終點(diǎn)作為起點(diǎn)）能到達(dá)的點(diǎn)，我們就可以由
d
f
s
(
u
,
l
)
dfs(u,l)
dfs(u,l) 轉(zhuǎn)到
d
f
s
(
v
,
d
i
s
[
u
]
+
l
?
d
i
s
[
v
]
?
e
d
g
e
2
[
i
]
.
l
e
n
)
dfs(v,dis[u]+l-dis[v]-edge2[i].len)
dfs(v,dis[u]+l?dis[v]?edge2[i].len)了。
邊界便為當(dāng)
i
≤
?
1
i \leq -1
i≤?1 或
i
≠
k
+
1
i \neq k + 1
i?=k+1時(shí)，返回
0
0
0;
但是，數(shù)據(jù)中有明顯的指示，有
0
0
0 邊！所以我們可以用一個(gè)
f
l
a
g
flag
flag 數(shù)組來標(biāo)記。
最后，我們可以將這個(gè)
d
f
s
dfs
dfs 記憶化，每個(gè)點(diǎn)和邊在一個(gè)
d
f
s
dfs
dfs 最多只會(huì)遍歷一次，所以時(shí)間復(fù)雜度為
O
(
n
O(n
O(n
l
o
g
(
n
+
m
)
+
k
(
n
+
m
)
)
log(n+m)+k(n+m))
log(n+m)+k(n+m))。
A
C
AC
AC
C
o
d
e
1
Code1
Code1:
#includeusing namespace std;
const int N = 2e5 + 1, M = 51;
struct node{int val, dis;
friend bool operator< (node x, node y) {return x.dis >y.dis;}
};
priority_queueq;
struct Edge{int to, next, len;
}edge[N<< 1], edge2[N<< 1];
int T, n, m, K, P, num, num2, head[N], head2[N], dis[N], vis[N], flag[N][M], dp[N][M];
void add(int x, int y, int z) {edge[++num] = (Edge){y, head[x], z}, head[x] = num; }
void adds(int x, int y, int z) {edge2[++num2] = (Edge){y, head2[x], z}, head2[x] = num2; }
void Dijkstra() {for (int i = 1; i<= n; ++i) vis[i] = 0, dis[i] = 1e9; dis[1] = 0;
q.push((node){1, 0});
while (!q.empty()){node tmp = q.top(); q.pop();
int u = tmp.val, l = tmp.dis;
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = edge[i].next){ int v = edge[i].to;
if (dis[v] >dis[u] + edge[i].len){ dis[v] = dis[u] + edge[i].len;
if (!vis[v]) q.push((node){v, dis[v]});
}
}
}
}
int dfs(int u, int l) {if (l< 0 || l >K) return 0;
if (flag[u][l]) return -1;
if (dp[u][l] != -1) return dp[u][l];
flag[u][l] = 1;
int sum = 0;
for (int i = head2[u]; i; i = edge2[i].next){int v = edge2[i].to;
int tmp = dfs(v, dis[u] + l - dis[v] - edge2[i].len);
if (tmp == -1) return -1;
(sum += tmp) %= P;
}
if (u == 1 && !l) ++sum;
dp[u][l] = sum, flag[u][l] = 0;
return sum;
}
int main() {scanf("%d", &T);
while (T--) {num = num2 = 0;
memset(head, 0, sizeof(head));
memset(head2, 0, sizeof(head2));
scanf("%d%d%d%d", &n, &m, &K, &P);
for (int i = 1, x, y, z;i<= m;i++) { scanf("%d%d%d", &x, &y, &z);
add(x, y, z), adds(y, x, z);
}
Dijkstra();
memset(dp, 255, sizeof(dp));
memset(flag, 0, sizeof(flag));
int ans = 0, flag = 0;
for (int i = 0; i<= K;i++) { int tmp = dfs(n, i);
if (tmp == -1){flag = 1; break;}
ans = (ans + tmp) % P;
}
if (!flag) printf("%d\n", ans);
else puts("-1");
}
return 0;
} 下面便是用
T
o
p
S
o
r
t
TopSort
TopSort 的做法，復(fù)雜度相同(別人的)（其實(shí)是
d
f
s
dfs
dfs 的作用）。
另外，
S
t
r
u
c
t
Struct
Struct 的封裝也很好。
A
C
AC
AC
C
o
d
e
2
Code2
Code2:
#includeconst int N = 1e5 + 10, M = 2e5 + 10, Nt = 131072, inf = 0x3f3f3f3f;
int ri() {char c = getchar(); int x = 0, f = 1; for(;c< '0' || c >'9'; c = getchar()) if(c == '-') f = -1;
for(;c >= '0' && c<= '9'; c = getchar()) x = (x<< 1) + (x<< 3) - '0' + c; return x * f;
}
int n, q[N], d[N], rk[N], f[N], g[N], *D, id[N], T[Nt<< 1], dp[51][N], K, P;
struct Edge {int nx[M], pr[N], to[M], w[M], tp;
void add(int u, int v, int W) {to[++tp] = v; nx[tp] = pr[u]; pr[u] = tp; w[tp] = W;}
void adds(int u, int v, int w) {add(u, v, w); add(v, u, w);}
void Pre() {for(int i = 1;i<= n; ++i) pr[i] = 0; tp = 0;}
}G, R;
int min(int a, int b) {return D[a]< D[b] ? a : b;}
bool cmp(int a, int b) {return f[a] == f[b] ? rk[a]< rk[b] : f[a]< f[b];}
void Up(int i, int v) {for(T[i += Nt] = v;i >>= 1;) T[i] = min(T[i<< 1], T[i<< 1 | 1]);}
void Dij(const Edge &G, int st) {for(int i = 0;i<= n; ++i) D[i] = inf;
D[st] = 0; Up(st, st);
for(;D[T[1]] != inf;) {int u = T[1]; Up(u, 0);
for(int i = G.pr[u], v, w; i; i = G.nx[i])
if(D[v = G.to[i]] >(w = D[u] + G.w[i]))
D[v] = w, Up(v, v);
}
}
bool Topsort() {int L = 1, R = 0;
for(int i = 1;i<= n; ++i)
if(!d[i])
q[++R] = i;
for(int u = q[L];L<= R; u = q[++L])
for(int i = G.pr[u]; i; i = G.nx[i])
if(!G.w[i] && !--d[G.to[i]])
q[++R] = G.to[i];
for(int i = 1;i<= R; ++i)
rk[q[i]] = i;
for(int i = 1;i<= n; ++i)
if(d[i] && f[i] + g[i]<= f[n] + K)
return false;
for(int i = 1;i<= n; ++i)
id[i] = i;
std::sort(id + 1, id + n + 1, cmp);
return true;
}
void Inc(int &a, int b) {a += b; if(a >= P) a -= P;}
void Dp() {memset(dp, 0, sizeof(dp));
dp[0][id[1]] = 1;
for(int k = 0;k<= K; ++k)
for(int x = 1, u = id[1];x<= n; u = id[++x])
for(int i = G.pr[u], w, v; i; i = G.nx[i])
if((w = f[u] + k + G.w[i] - f[v = G.to[i]])<= K)
Inc(dp[w][v], dp[k][u]);
}
int main() {for(int C = ri();C--;) {n = ri(); int m = ri(); K = ri(), P = ri();
G.Pre(); R.Pre();
for(int i = 1;i<= n; ++i)
d[i] = rk[i] = 0;
for(int u, v, w;m--;)
u = ri(), v = ri(), w = ri(),
G.add(u, v, w), R.add(v, u, w), d[v] += !w;
D = f; Dij(G, 1);
D = g; Dij(R, n);
if(!Topsort()) { puts("-1"); continue;
}
Dp();
int r = 0;
for(int i = 0;i<= K; ++i) Inc(r, dp[i][n]);
printf("%d\n", r);
}
return 0;
}
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
