Problem1616--图-Floyd最短路

1616: 图-Floyd最短路

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 281  Solved: 105
[Status] [Submit] [Creator:]

Description

输入一个有向图，包含n（n<=10^2)个节点，m(m<=10^3)条有向边，所有边的长度w范围为 0<w<=100，题目确保没有自环，但可能有重边。
输出从1号节点到n号节点的最短距离。

Input

第一行n，m，有n个点，m条边，
以下m行每行3个正整数，表示每条边连接的起点，终点和长度。

Output

1号节点到n号节点的最短路径，若无法到达输出-1

Sample Input Copy 

5 4
1 2 10
2 3 10
3 4 10
4 5 10

Sample Output Copy 

40

Source/Category

 提高A  
[Submit] [Status]