OpenJudge

3:HSYOI 城市交通

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
128000kB
描述

某城市有n个街道,某些街道有公共汽车线路相连,在图中,街道12之间有一条公共汽车线路相连,且有街道1至街道2的时间为34分钟。由于街道与街道之间的距离较近,与等车的时间相比可以忽略不记,所以这个时间为两趟公共汽车的间隔时间,即平均的等车时间。如图,由街道1至街道5的最快走法为1-3-5,总时间为44分钟。现在,市政府为了提高城市的交通质量,决定加开m条线路。若在某两个街道a,b之间加开线路(距离未变,只是等车的时间缩短一半)。例如,若在12之间加开一条线路,则时间变为17分钟,加开两条线路,时间变为8.5分钟,依次类推。所有的线路都是环路,即如果由12的时间变为17分钟,则由21的时间也变为17分钟求加开某些线路,能使城市1至城市n的时间最少。例如在下图中,如果m=2,则改变1-33-5的线路,总的时间可以减少22分钟。



输入
第一行城市数n 50 以内和加开线路数m 10以内。
第二行至第n+1行 每行为n个数,第i+1行第j列表示又城市i到城市j的时间(如果为0,则城市i不可能到城市j。)
注意:输入数据中,从城市1到城市n至少有一条路线。
输出
第一行由城市1到城市n的最小时间X(小数点后保留两位)。
第二行至第 m+1行 更改的路线。每行有两个整数(x,y)构成。表示在城市x与城市y之间增加的一条路线,按字典序。
样例输入
5 2
0 34 24 0 0
34 0 10 12 0
24 10 0 16 20
0 12 16 0 30
0 0 20 30 0
样例输出
22.00
1 3
3 5
全局题号
10891
添加于
2016-07-08
提交次数
4
尝试人数
3
通过人数
3