首页 | 题库 赛题 | 状态 比赛 | 排行 讨论 题解 | 团队 主题 个人信息 消息 注销 | OIBH 赞助我们
Announcement : RQNOJ经费不足,带宽较小,网络卡的时候请不要重复刷新.RQNOJ添加题目规则公布
查看题目 Show Problem
题目:倒霉的飞翔
问题编号:471 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
My Flag:Unsubmited
题目类型
尚未设置
描述
飞翔很倒霉，在这放假期间也不能休息，被迫找了个兼职帮着发传单⊙﹏⊙汗，然而更倒霉的是，他必须去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!”（不包括双引号）。
样例输入
4 3
1 2 10
2 3 15
3 1 10
3
1 3
3 2
1 4
样例输出
25
20
Fei Xiang can’t find the second shortest way!