题目描述(ID:12120)
标题: 极品飞车
标签: 数据结构 搜索 并查集 枚举
详情:
  Hecy被FC星人劫持了!,原来Hecy被劫持的原因是FC星人看中了他的编程才能“ FC星有许多城市,某些城市之间无法直接到达,但某些城市之间可以通过一种奇怪的高速公路SARS(Super Air Roam Structure 超级空中漫游结构)进行人员或物资的交流运输。在SARS上有且仅有一种“车”可以行驶,那就是传说中的极品飞车Flycar。东东们就是乘坐着Flycar在SARS上运动的。与地球相似地,每条SARS都对行驶在他上面的Flycars有限速要求——不同的是这既不是限最高速,也不是限最低速,而是限固定速,也就是说Flycars必须以所限速度行驶,否则就要被TS(Traffic System)来一次ts(tiger strike虎击)——这可不是好玩的!
  同时FC星人对flycar的“舒适度”也有特殊的要求。他们认为乘坐一次flycar过程中,flycar达到的最高速与最低速之间的差越小,本次乘坐越舒适(可以理解,因为SARS的限速要求,flycar都必须瞬间提/降速,痛苦啊)——FC星人对时间却没那么多要求。

        因此Hecy的任务就明确了:为FC星上几乎垄断了flycar市场的全星通用汽车公司(CC)设计新一代自动寻路flycar,使得该flycar能自动寻找两城市间最舒适的到达路径。
        注意:SARS是双向的。
输入格式:
数据的第一行有2个正整数n(1 < n < 201)与m(m < 1001),表示有n个城市m条SARS。接下来的m行每行有三个正整数StartCity,EndCity,Speed,分别表示有条SARS从StartCity出发到达EndCity,限速Speed(城市标号在1到n之间)。然后是一个非负整数Q(Q < 11),表明寻路要求的个数。接下来的Q行每行有2个正整数Start与End,表明需要寻路的起终点。
输出格式:
对每个寻路要求打印一行,该行为一个非负整数,表明最佳路线的舒适度(最高速与最低速的差)。
样例:

输入

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

输出

1
0
登录并解答