#CW78. 迷宫游戏(maze)

迷宫游戏(maze)

题目描述

迷宫有 NN 个房间,房间编号为 1,2,…,N1, 2, \ldots, N。Ai=1A_i = 1 表示房间 ii 有出口,Ai=0A_i = 0 表示没有出口。恰有 MM 对房间之间存在无向通道;对于第 ii 对房间 ai,bia_i, b_i,有 cic_i 条互不相同的通道连接这两个房间。不保证任意两个房间之间都能通过通道相互到达。

一次游戏给出起点 ss 和整数 kk。Alice 最初位于房间 ss。每轮她在当前房间 xx 选择恰好 kk 条与 xx 相连且互不相同的通道;即使连接同一对房间,也可以选择其中的多条不同通道。如果与 xx 相连的通道总数少于 kk,Alice 立即输掉游戏。随后 Bob 从 Alice 所选的 kk 条通道中选择一条,Alice 沿该通道移动到另一端的房间。

Alice 可以重复上述过程任意多次,包括 0 次;一旦到达有出口的房间,她立即获胜。若起点 ss 本身有出口,则无需移动即可获胜。Alice 尽力获胜,Bob 尽力阻止她。若存在一种策略,使得无论 Bob 如何选择,Alice 最终都能到达有出口的房间,则她能够获胜;否则她无法获胜。请对每局游戏判断 Alice 是否能够获胜。

输入格式

从 maze.in 文件中读入。

第一行包含 N,M,QN, M, Q,分别表示房间数、存在通道的房间对数和游戏局数,满足 1≤N≤2000001 \le N \le 200000、0≤M≤4000000 \le M \le 400000、1≤Q≤2000001 \le Q \le 200000。第二行包含 NN 个 Ai∈{0,1}A_i \in \{0, 1\},表示各房间是否有出口。接下来 MM 行包含 ai,bi,cia_i, b_i, c_i,表示房间 ai,bia_i, b_i 之间有 cic_i 条通道,满足 1≤ai<bi≤N1 \le a_i < b_i \le N、1≤ci≤1091 \le c_i \le 10^9;任意两行给出的房间对不同。最后 QQ 行包含 sj,kjs_j, k_j,分别表示第 jj 局游戏的起点和每轮必须选择的通道数,满足 1≤sj≤N1 \le s_j \le N、1≤kj≤10181 \le k_j \le 10^{18}。

输出格式

向 maze.out 文件中输出。

输出 QQ 行;第 jj 行若 Alice 能在第 jj 个游戏中获胜则输出 YES,否则输出 NO。

样例 1 输入

5 5 5
0 0 1 0 0
1 2 1
1 3 1
1 4 2
2 3 2
3 4 1
2 1
1 2
3 3
4 4
5 1

样例 1 输出

YES
YES
YES
NO
NO

样例 2 输入

4 3 4
1 0 0 0
1 2 2
2 3 3
3 4 1
1 3
2 2
3 3
4 1

样例 2 输出

YES
YES
NO
YES

样例 3 输入

4 3 3
0 1 1 0
1 2 1
1 3 3
1 4 2
4 2
1 3
4 3

样例 3 输出

YES
YES
NO

样例 4 输入

2 0 2
1 0
1 1
2 1

样例 4 输出

YES
NO

数据范围

所有输入数据均为整数。

本题采用子任务捆绑计分:通过一个子任务的全部测试点,才能获得该子任务的分数。

子任务 分值 测试点 附加条件
1 6 1∼21 \sim 2 图为链:M=N−1M = N - 1,第 ii 条通道连接 ii 与 i+1i + 1,且仅房间 1 为出口
2 8 3∼43 \sim 4 图为星:M=N−1M = N - 1,每条通道连接房间 1 与某个房间 i+1i + 1
3 7 5∼65 \sim 6 k1=k2=⋯=kQ=1k_1 = k_2 = \cdots = k_Q = 1
4 14 7∼97 \sim 9 k1=k2=⋯=kQk_1 = k_2 = \cdots = k_Q
5 15 10∼1210 \sim 12 s1=s2=⋯=sQs_1 = s_2 = \cdots = s_Q
6 16 13∼1513 \sim 15 N,M≤3000N, M \le 3000,且所有 kj≤3000k_j \le 3000
7 34 16∼2016 \sim 20 无额外限制