SDUT 2894 C--最短路

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