6688: 分数调查
[Creator : ]
Description
小周周的班级总共有 $N$ 名学生,编号 $1 \sim N$。学校刚刚进行了一场全校的古诗文水平测验。
但是老师没有公布测验的成绩,所以小周周只能得到一些小道消息,例如 $X$ 号同学的分数比 $Y$ 号同学的分数高 $S$分。
小周周想知道利用这些消息,能不能判断出某两位同学之间的分数高低?
但是老师没有公布测验的成绩,所以小周周只能得到一些小道消息,例如 $X$ 号同学的分数比 $Y$ 号同学的分数高 $S$分。
小周周想知道利用这些消息,能不能判断出某两位同学之间的分数高低?
Input
第一行包含三个整数 $N, M, Q$。$N$ 表示学生总数,$M$ 表示小周周知道消息的总数,$Q$ 表示小周周想询问的数量。
以下 $M$ 行每行三个整数,$X, Y, S$。表示 $X$ 号同学的分数比 $Y$ 号同学的分数高 $S$ 分。
以下 $Q$ 行每行两个整数,$X,Y$。表示小周周想知道 $X$ 号同学的分数比 $Y$ 号同学的分数高几分。
以下 $M$ 行每行三个整数,$X, Y, S$。表示 $X$ 号同学的分数比 $Y$ 号同学的分数高 $S$ 分。
以下 $Q$ 行每行两个整数,$X,Y$。表示小周周想知道 $X$ 号同学的分数比 $Y$ 号同学的分数高几分。
Output
对于每个询问,如果不能判断出 $X$ 比 $Y$ 高几分输出 $-1$。否则输出 $X$ 比 $Y$ 高的分数。
Constraints
对于 $50\%$ 的数据,$1 \leq N, M, Q \leq 1,000$
对于 $100\%$ 的数据,$1 \leq N, M, Q \leq 100,000,\ 1 \leq X, Y \leq N,\ -1,00 \leq S \leq 1,00$
数据保证没有矛盾。
对于 $100\%$ 的数据,$1 \leq N, M, Q \leq 100,000,\ 1 \leq X, Y \leq N,\ -1,00 \leq S \leq 1,00$
数据保证没有矛盾。
Sample 1 Input
10 5 3
1 2 10
2 3 10
4 5 -10
5 6 -10
2 5 10
1 10
1 5
3 5
Sample 1 Output
-1
20
0
Sample 2 Input
5 4 10
1 2 10
2 3 10
3 4 10
4 5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Sample 2 Output
10
20
30
40
10
20
30
10
20
10