Posted on 2013-06-12 19:26
happyac 阅读(1311)
评论(0) 编辑 收藏 引用 所属分类:
uva
总结
图论问题，经过简单的分析，其实是一个单源最短路径问题。
分析
There will be at most two intersections with odd degree
说明存在欧拉通路（
Eulerian path）。有两种情况：
所有交点的度（Degree）都为偶数。
那么就存在欧拉回路（Eulerian circuit）。最短路程就是所有边长之和。
有且只有两个交点有奇数度（Degree）
那么这两个交点就是欧拉通路的起点和终点。接下来只要找到这两点之间的最短路径，最终最短路程就是所有边长之和加上这两点的最短路径长度。