2307. [CTSC 2016] NOIP十合一

【题目描述】

在 NOIP 2044 的赛场上，小D遇到了这样一道题：

给出一个 n 个点的图，其中有 m 条带权有向边，有 q 个询问，每个询问形如从 u 号点走到 v 号点，长度为 W 的道路数量有多少？你只需要输出答案对 P 取模的结果即可。

小D思考了良久也不会做这道题，悻悻离场之后，他从官网上取得了这道题的数据，共有 10 组数据。小D怎么也想做出来这道题，于是他开始寻求你的帮助，将 10 组数据的输入给了你。聪明的你一定可以帮小D计算出每组数据的输出的!

【输入格式】

每个输入文件的第一行包括 4 个正整数 n,m,q,P，表示图中点数、边数、询问数目及模数。点的编号为从 1 到 n 的整数。

接下来 m 行描述 m 条带权有向边，其中第i行包含3个整数 ai,bi,ci，表示第i条边起点为 ai，终点为 bi，权值为 ci。

接下来 q 行描述询问，其中第 k 行包含 3 个整数 uk,vk,wk，表示第 k 个询问需要输出从 uk 号点走到 vk 号点，长度为 wk 的道路数量对 P 取模的结果。

【输出格式】

每个输出文件中不超过 q 行，每行包含一个小于 P 的非负整数，表示该测试点前 q 个询问的答案。 

【样例输入】

3 4 2 10
1 1 2
1 2 2
1 3 1
2 3 3
1 3 5
1 3 3

【样例输出】

2
1

【样例说明】

对于第一组询问，一共有两条从 1 号点到 3 号点、长度为 5 的路径。假定边的编号从 1 至 4，则这两条路径经过的边为：

第 1 条：2 -> 4；

第 2 条：1 -> 1 -> 3。

【子任务及部分分】

测试点部分输出下载

每个测试点单独评分。每个测试点你还可能获得部分分。

最终评测时，我们将根据你在每个数据中回答正确的询问个数进行计分。

如果你的输出不超过 q 行，且每行只包含一个不超过 P 的非负整数，在最终评测时我们将认为你在第 i 行的输出是在回答对应测试点的第 i 个询问。

对于每个测试点，我们设置了10个评分参数 a1,a2,a3,…,a9,a10。在你的方案中，若正确回答的询问个数为 wuser，你的分数将会由下表给出(若符合表中多个条件，取分数最高的)：

【提示】

【来源】

CTSC2016 D1T3