SDUT 2894 C–最短路

Time Limit: 7000MS Memory Limit: 65536KB

PRoblem Description

給出一個帶權無向圖，包含n個點，m條邊。求出s，e的最短路。保證最短路存在。

Input

多組輸入。 對于每組數據。 第一行輸入n，m(1<= n && n<=5*10^5,1 <= m && m <= 2*10^6)。 接下來m行，每行三個整數，u,v,w,表示u，v之間有一條權值為w(w >= 0)的邊。 最后輸入s，e。

Output

對于每組數據輸出一個整數代表答案。

Example Input

3 1 1 2 3 1 2

Example Output

3

Hint

spfa算法：http://blog.csdn.net/muxidreamtohit/article/details/7894298 前向星：http://blog.csdn.net/acdreamers/article/details/16902023

Submit