POJ3463【次短路】

转自：http://www.cnblogs.com/jackge/archive/2013/04/29/3051273.html

算法：最短路和次短路。Dijkstra算法。采用邻接表建图。

总结：不要用邻接矩阵。因为有重边。

dis[x][2]:dis[x][0]表示起点到x的最短路、dis[x][1]表示起点到x的次短路；

arr[x][2]:arr[x][0]表示起点到x的最短路条数、arr[x][1]表示起点到x的次短路的条数；

vis[x][2]对应于x和0、1功能为记录该点是否被访问！

那么如何更新最小和次小路呢？显然我们容易想到下面的方法：

      1.if(x<最小)更新最小，次小；
      2.else if(x==最小)更新方法数；
      3.else if(x<次小)更新次小；
      4.else if(x==次小)更新方法数；