#P17819. [ONTAK 2023]WPA
[ONTAK 2023]WPA
题目描述
给定一个有向无环图,共有 个顶点和 条带正整数权的边。顶点编号为 到 ,每条边都从编号较小的顶点指向编号较大的顶点。允许同一对端点之间有多条边。
有 个询问。每个询问给出 ,请判断是否存在一条从顶点 到顶点 的路径,其总长度 满足
右端点不向上取整;等价地,整数 必须满足 。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例的第一行包含 。 接下来 行,每行三个整数 ,表示一条长度为 的边 。 接下来 行,每行两个整数 ,表示一个询问。
输出格式
每个测试用例输出一行长度为 的字符串。第 个字符为 1 表示对应询问有解,否则为 0。
数据范围
;每个测试用例中:
- ,,;
- ,;
- ,。
同一个输入文件中,所有测试用例的 之和、 之和、 之和各自不超过 。
样例
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