讨论 / 高分悬赏此题解法
雨凌 2009-11-12 17:48:00
点我顶贴 收藏 删除

首页 | 题库 赛题 | 状态 比赛 | 排行 讨论 题解 | 团队 主题 个人信息 消息 注销 | 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!

#1 webeskycn@2009-11-11 16:28:00
回复 删除
先求最短路然后枚举边删掉?(我猜的...- -)

这比赛也没解题报告...

#2 雨凌@2009-11-12 17:48:00
回复 删除
up
查看更多回复
提交回复