1344_Alice拜年

大年初一，Alice带上拜年礼物去给N-1位亲朋好友长辈拜年，亲友真多啊，是个大家族。由于Alice才2岁，力气不大，每次只能拿一份礼物，拜完年之后，要回家取第二份礼物，然后去下一家拜年（无语了）。为了表示对亲朋长辈的尊敬，Alice每次都从家步行去到对方家里，拜完年由爸爸骑自行车带回家（彻底无语）。可怜天下父母心啊，爸爸全程陪着Alice折腾。

假设Alice的住址编号为1，各亲朋好友的家分别编号为 2 ~ N 。这个城市的道路都是单向的（别惊奇，这个世界无奇不有），共有M条道路，每条道路长短不一。求Alice给这 N-1 个家庭拜完年，最少步行了多少路程？

输入的第一行是两个整数 N 和 M，1 ≤ N ≤ 1000， 1 ≤ M ≤ 100000

接下来M行，每行3个正整数 U ，V ，W ，表示该条道路是从节点U到节点V的，这条道路共有W米。满足 1 ≤ U, V ≤ N ， 1 ≤ W ≤ 10000 ，保证任意两点都能互相到达。

注意本题有重边。

输出一行，包含一个整数，为Alice最少步行的路程。

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

28

单源最短路径算法小结

这里就不写具体算法了，只将他们的时间复杂度、适用范围、代码复杂程度简单做个比较
待搜索的图都指有向图(无向图类似)。储存方式均为邻接表

一、广度优先搜索(BFS)
时间复杂度：O(V+E)，效率很高
适用范围：(很窄)仅适于无权边的图。即每条边长度都为1的情况
代码复杂程度：一般，需队列

二、Bellman-Ford
时间复杂度：O(VE)，效率一般
适用范围：(很广)允许存在负权边，能够判断图中是否存在从源点可到达的负权环路
代码复杂程度：较易

三、有向无环图算法
时间复杂度：O(V+E)，效率很高
适用范围：(很窄)仅适于有向无环图
代码复杂程度：一般，需拓扑排序

四、Dijkstra
适用范围：(一般)不允许存在负权边
这个算法复杂度取决于"取最小"(Extract-min)操作使用的算法
      Extract-min操作                时间复杂度               代码复杂程度
顺序检测所有点决定最小值           O(V^2)                        一般
使用Binary-Heap(优先队列)       O((V+E)lgV)                 较复杂
   使用Fibonacci-Heap               O(VlgV+E)                  较复杂

五、SPFA (Shortest Path Faster Algorithm)
时间复杂度：O(kE)，k为一较小常量。效率很高
适用范围：(较广)，允许存在负权边，但不允许负权环路
代码复杂程度：较易，需队列
这个算法可算是 Bellman-Ford 的优化版本，去除冗余的Relax操作，效率有很大提升

      有些奇怪的是这个算法在《算法导论》和 Wikipedia 上竟然都没有介绍，而只在国内的OI相关网站论坛才发现的解释，大多还不是很全面。从适用范围和代码复杂程度来看绝对是一个值得推荐的算法(比熟知的Dijkstra都要好)，效率上也不比使用 Heap 优化的 Dijkstra 低，一般来说甚至还要高(还有待更多题目实践验证)。即使寻找所有顶点对之间的最短路径这个算法也是值得考虑的(对每个顶点运行一次SPFA)。