PID471 / 倒霉的飞翔
题目描述

飞翔很倒霉,在这放假期间也不能休息,被迫找了个兼职帮着发传单⊙﹏⊙汗,然而更倒霉的是,他必须去N个城市去发,而且老板规定不能走最短路线(什么老板啊........),所以他只好找比最短路长但又尽可能短的路了。

给出N个城市,和M条通道,和走这M条通道的长度。并且给出Q,提问Q次,每次提问,给出起始城市的编号和终止城市的编号,输出这两个城市之间的第二短路。

对于20%的数据,有1<=N<=10,1<=Q<=10;

对于50%的数据,有1<=N<=50,1<=Q<=500;

对于100%的数据,有1<=N<=160,1<=Q<=10000,所有道路长度不超过2^10-1。

输入格式

第一行2个数n,m(意义如上所示)

接下来M行,每行3个数,a,b,c,表示a到b有一条长度为c的道路。(2个城市之间最多出现一条道路)。

接下来一行Q

接下来Q行,每行2个数,u,v,即起始和终止城市的编号。

输出格式

对应输出Q行,如果存在第二短路,则输出该长度,否则输出“Fei Xiang can't find the second shortest way!”(不包括双引号)。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论