#734. 货车运输

    ID: 734 传统题 1000ms 128MiB 尝试: 3 已通过: 0 难度: 10 上传者: 标签>贪心数据结构并查集树结构生成树图结构最小生成树竞赛NOIP年份2013提高倍增最近公共祖先LCA

货车运输

题目描述

A 国有 n\red{n} 座城市,编号从 1\red{1}n\red{n},城市之间有 m\red{m} 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q\red{q} 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。

输入格式

输入文件第一行有两个用一个空格隔开的整数 n\red{n}m\red{m},表示 A 国有 n\red{n} 座城市和 m\red{m} 条道路。

接下来 m\red{m} 行每行 3\red{3} 个整数 x\red{x}y\red{y}z\red{z},每两个整数之间用一个空格隔开,表示从 x\red{x} 号城市到 y\red{y} 号城市有一条限重为 z\red{z} 的道路。注意:x\red{x} 不等于 y\red{y},两座城市之间可能有多条道路。

接下来一行有一个整数 q\red{q},表示有 q\red{q} 辆货车需要运货。

接下来 q\red{q} 行,每行两个整数 x\red{x}y\red{y},之间用一个空格隔开,表示一辆货车需要从 x\red{x} 城市运输货物到 y\red{y} 城市,注意:x\red{x} 不等于 y\red{y}

输出格式

输出共有 q\red{q} 行,每行一个整数,表示对于每一辆货车,它的最大载重是多少。如果货车不能到达目的地,输出 1\red{-1}

样例

样例输入 1\red1

4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3

样例输出 1\red1

3
-1
3

数据范围与提示

对于 30%\red{30\% }的数据,0<n<1000\red{0 < n < 1\,000}0<m<10000\red{0 < m < 10\,000}0<q<1000\red{0 < q < 1\,000}

对于 60%\red{60\% }的数据,0<n<1000\red{0 < n < 1\,000}0<m<50000\red{0 < m < 50\,000}0<q<1000\red{0 < q < 1\,000}

对于 100%\red{100\%} 的数据,0<n<10000\red{0 < n < 10\,000}0<m<50000\red{0 < m < 50\,000}0<q<30000\red{0 < q < 30\,000}0z100000\red{0 \leq z \leq 100\,000}