题目描述(ID:12251)
标题: 极品飞车
标签:
详情: [ 问题描述 ] 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 能自动寻找两城市间最舒适的到达路径。
输入格式:
数据的第一行有 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,表明需要寻路的起终
点。
输出格式:
对每个寻路要求打印一行,该行为一个非负整数,表明最佳路线的舒适
度(最高速与最低速的差)。
提示: SARS 是双向的
样例:

输入

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

输出

1
0
登录并解答