P2495【NOIP2013-D1T3】货车运输 | |
|
问题描述
A国有n座城市,编号从1到n,城市之间有m条双向道路。
每一条道路对车辆都有重量限制,简称限重。
现在有q辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。
输入格式
第一行有两个用一个空格隔开的整数 n,m,表示 A 国有n座城市和m条道路。
接下来m行,每行3个整数x,y,z,表示从x号城市到y号城市有一条限重为z的道路(x≠y,两座城市之间可能有多条道路)
接下来一行有一个整数 q,表示有 q 辆货车需要运货。
接下来q行,每行两个整数x,y,之间用一个空格隔开,表示一辆货车需要从x城市运输货物到y城市(x≠y)。
输出格式
输出共有 q 行,每行一个整数,表示对于这一辆货车,它的最大载重是多少。
如果货车不能到达目的地,输出-1。
样例输入 1
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
样例输出 1
3
-1
3
样例输入 2
5 7
4 3 4440
3 1 22348
1 3 28368
2 4 25086
5 3 6991
4 3 10638
3 1 11106
4
4 5
1 3
5 4
2 5
样例输出 2
6991
28368
6991
6991
提示
对于 30%的数据,1<=n<=1000,1<=m<=10000,1<=q<=1000;
对于 60%的数据,1<=n<=1000,1<=m<=50000,1<=q<=1000;
对于 100%的数据,1<=n<=100000,1<=m<=500000,1<=q<=30000,0<=z<=100000。