ZJU/ZOJ 1456 Minimum Transport Cost 解题报告

求给出的两点间的最短路径，如果有多条最短路径要求输出字典序最小的。

由于给的是稠密图所以首选朴素的Dijkstra算法，但是由于要问多个点对之间的最短路径，所以实际上用Floyd的效率更高。注意字典序最小这一限制条件的处理方法，因为对这一条件的处理错误WA了很久……我的处理方法是用next[i,j]表示从i到j的短路径的最近中间点，遇到经某个中间点与已知最短路径距离相等时倒推求出第一个不同的点，比较大小来判断是否进行next数组的更新操作。

3009127 2008-07-27 18:10:39 Accepted 1456 FPC 00:00.01 424K IwfWcf