1028. 路由器

单点时限: 2.0 sec

内存限制: 256 MB

路由器是网络中用来转发 IP 报文的一种设备。

当路由器收到一个终端或者其它路由器发过来的报文时,它必须选项择最快的一条通信线路通向报文所指向的目标机器(目标机器可能是一个终端,也可能是另一个路由器)。众所周知,在两个路由器之间可能有多条通信线路,你的任务就是给出两个路由器之间最短通信时间。

每一个路由器都有一个 IP 来标识它自己,这个标识是唯一的。任意两点之间的通信时间单位是毫秒。每条通信线路都是全双工的 (双向的)。

输入格式

第一行为两个整数 n 和 m,n 表示有多少个路由器,m 表示有多少条通信线路。(2<=n<=100,1<=m<=1000)

接下去的 m 行用来描述路由器之间的线路。每行包括三个元素,两个路由器的 IP 地址和它们之间通信所花费的时间。

然后一行是一个整数 t,表示有多少个报文。(1<=t<=1000)

接下去的 t 行是报文。每个报文占一行,为了简化问题,我们在每行中给出两个 IP 地址,分别是目标地址和源地址。你要做的就是求出两者之间的最短时间。

输出格式

对于每个报文,输出一行。每行只包含一个整数,表示报文给的两个 IP 地址之间的最短通信时间。如果不存在这样的通路,或者 IP 地址并不存在,则输出-1。

样例

Input
4 5
168.120.1.1 168.120.1.2 15
168.120.1.1 168.120.1.4 47
168.120.1.1 168.120.1.3 10
168.120.1.2 168.120.1.4 15
168.120.1.3 168.120.1.4 25
3
168.120.1.1 168.120.1.4
168.120.1.3 168.120.1.4
168.120.1.3 202.12.12.12
Output
30
25
-1

260 人解决,313 人已尝试。

386 份提交通过,共有 928 份提交。

2.2 EMB 奖励。

创建: 13 年,11 月前.

修改: 1 年,9 月前.

最后提交: 2 周,1 天前.

来源: 2005计算机系程序设计竞赛

题目标签