OI题库

Source: GZOI2011  Rail

提交文件：highrail.cpp/c/pas

输入文件：highrail.in

输出文件：highrail.out

题目描述：

你所在的省刚获得国家拨款兴建高铁，高铁的起止城市是国家选定的，中途可能经过若干城市。根据国家拨款的政策，国家将负担费用最大的两个区间，其余的必须由省负担。假如高铁线路中途只经过一个城市，国家只负担费用较大的区间。假如是直达的，国家将不负担任何费用。

你被省里选定作为这个项目的总工程师，你必须规划出一条高铁线路，使得省负担的费用最少。当然，路线上每个城市最多只经过一次。

输入格式（ highrail .in）：

第一行是一个正整数n，n<=50，代表城市之间的高铁建设费用估算（注意并非每对城市之间的建设费用都进行了估算）。接下来n行是用空格分隔的三个整数s,e,c。s和e代表城市的编码，高铁的起点和终点城市分别是编码为0和1，其余的城市依次编码。c<=1000，是在s和e之间建设费用估算，从s到e与从e到s的建设费用是相同的。

输出格式（ highrail .out）：

输出只有一行，格式为c1 c2 … cm cost，各数字用一个空格分隔，代表高铁线路规划和省负担的费用。ci代表城市编码（注意c1=0，cm=1），cost是费用。我们保证输入肯定有解，如果有多个解，输出当中经过城市最少的解，如果仍有多个解，则输出当中按字典序排列最小的解。

样例

highrail.in	highrail.out
7 0 2 10 0 3 6 2 4 5 3 4 3 3 5 4 4 1 7 5 1 8	0 3 4 1 3