[QBXT图论欢乐赛]神经

[QBXT图论欢乐赛]神经

题目背景

神经网络在人工智能领域大火,所以小悠学习了些许关于神经的知识。

题目描述

神经网络可以表示为\(N\)个点\(M\)条边的有向图,每个结点带有一个兴奋权值\(w_i\)
如果以x单位大小的电流刺激结点\(v\),设\(v_1,v_2,...,v_k\)是从\(u\)出发可以到达的结点,则神经网络会产生
\(T=x \times max\{w_{v_1},w_{v_2},w_{v_3},...,w_{v_n}\}\)的兴奋度,请注意,我们认为从u出发可以到达\(a\)。
现在请你回答若干询问,每个询问表示为:在以\(x\)大小的电流刺激\(v\)点后,网络的兴奋度是多少。

输入格式

每个测试点包含多组数据。
第一行,一个整数\(T\)表示数据组数,之后依次输入每组数据。
每组数据第一行,\(N\),\(M\),\(K\)分别表示点数,边数,询问次数。
之后一行,\(N\)个整数,\(w_1,w_2,...,w_N\)表示每个点的兴奋权值
之后\(M\)行,每行\(t_i,v_i\)表示一条从\(u_i\)到\(v_i\)的单向边。
之后\(K\)行,每行\(u_i,x_i\)表示一次刺激。

输出格式

对于每个测试点中的每个询问,输出一行一个整数表示答案。

样例输入

3
5 10 5
4 10 8 1 10
1 3
1 4
1 5
1 3
2 1
2 5
4 3
4 3
4 5
5 1
1 4
4 6
1 9
4 7
2 9
5 10 5
2 8 8 10 10
2 1
2 3
3 2
3 4
3 1
3 2
3 4
4 1
5 4
5 1
1 4
2 3
4 7
3 10
1 5
5 10 5
9 9 8 2 1
1 5
1 5
2 1
2 4
2 4
2 4
3 2
3 1
4 3
4 3
5 9
3 9
2 7
5 1
5 4

样例输出

40
60
90
70
90
8
30
70
100
10
9
81
63
1
4

数据范围

对于所有数据,\(T<5\),时间限制\(1000ms\),内存限制\(1GB\)
对于\(50%\)的测试点,\(N \le 1000,M \le 2000,K \le 1000\)。
对于\(20%\)的测试点,\(N<100000,M \le 200000 , x \le 100000\)输入的有向图构成\(DAG\)。
对于\(30%\)的测试点,\(N \le 200000,M \le 400000,K \le 100000\)
所有\(0 < x,w_i \le 10^9\)。

信息

ID
1398
难度
9
分类
(无)
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
1
上传者