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==次小)更新方法數；