2136: 宝典2第十一章城市交通

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

【题目描述】城市交通(traffic.cpp/c/pas)

魔法学院有n(1≤n≤50)个街区,某些街区有公共汽车线路相连,如图所示,街区1和2有一条公共汽车线路相连,且由街区1至2的时间为34分钟,由街区1至街区5最快走法是1→3→5,总时间为44分钟。

魔法学院为了改善交通,决定增加m(1≤m≤10)条公共汽车线路,若在某两街区a和b之间加开线路(前提是a和b之间必须已有线路),则从a到b的通行时间缩小为原来一半,例如,若在1和2之间加开一条线路,时间变为17分钟,若加开两条线路,时间变为8.5分钟,依次类推,所有的线路都是环线,即如果由1至2时间变为17分钟,则由2至1的时间也变为17分钟。求加开某些线路,能使由1至n的时间最少。例如,m=2,则加开1~3,3~5的线路,总时间可以减少为22分钟。求加开哪些线路,可使街区1到n的时间最短,并输出增加的线路。

【输入格式】

第一行为街区数n和增加公共汽车线路数m。

随后的每一行三个整数x,y,d,表示x街区到y街区的通行时间d。

【输出格式】

第一行为从街区1到街区n的最短时间。

随后m行表示增加的线路,线路需按前后顺序依次输出。

【输入样例】

5 2

1 2 34

1 3 24

2 3 10

2 4 12

3 4 16

3 5 20

4 5 30

【输出样例】

22

1 3

3 5

加入题单

上一题 下一题 算法标签: