#P17819. [ONTAK 2023]WPA

[ONTAK 2023]WPA

题目描述

给定一个有向无环图,共有 nn 个顶点和 mm 条带正整数权的边。顶点编号为 11 到 nn,每条边都从编号较小的顶点指向编号较大的顶点。允许同一对端点之间有多条边。

有 qq 个询问。每个询问给出 f,rf,r,请判断是否存在一条从顶点 11 到顶点 ff 的路径,其总长度 LL 满足

r≤L≤r⋅pp−1.r\le L\le r\cdot\frac{p}{p-1}.

右端点不向上取整;等价地,整数 LL 必须满足 (p−1)L≤pr(p-1)L\le pr。

输入格式

第一行一个整数 tt,表示测试用例数。

每个测试用例的第一行包含 n,m,q,pn,m,q,p。 接下来 mm 行,每行三个整数 ui,vi,diu_i,v_i,d_i,表示一条长度为 did_i 的边 ui→viu_i\to v_i。 接下来 qq 行,每行两个整数 fi,rif_i,r_i,表示一个询问。

输出格式

每个测试用例输出一行长度为 qq 的字符串。第 ii 个字符为 1 表示对应询问有解,否则为 0。

数据范围

1≤t≤10001\le t\le1000;每个测试用例中:

  • 2≤n≤5000002\le n\le500000,1≤m,q≤5000001\le m,q\le500000,2≤p≤202\le p\le20;
  • 1≤ui<vi≤n1\le u_i<v_i\le n,1≤di≤10111\le d_i\le10^{11};
  • 2≤fi≤n2\le f_i\le n,1≤ri≤10171\le r_i\le10^{17}。

同一个输入文件中,所有测试用例的 nn 之和、mm 之和、qq 之和各自不超过 500000500000。

样例

2
3 3 5 20
1 2 20
2 3 1
1 3 10
2 19
2 20
3 20
3 21
3 9
7 10 5 5
1 2 15
1 3 10
2 4 21
3 4 30
2 5 14
3 5 31
4 6 3
5 6 14
1 7 39
5 7 13
7 42
7 43
7 44
5 39
6 44
11110
10111