F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:祝各位Oier新年快乐,Rp++!
Problem 4289. -- PA2012 Tax

4289: PA2012 Tax

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 706  Solved: 224
[Submit][Status][Discuss]

Description

给出一个N个点M条边的无向图,经过一个点的代价是进入和离开这个点的两条边的边权的较大值,求从起点1到点N的最小代价。起点的代价是离开起点的边的边权,终点的代价是进入终点的边的边权
N<=100000
M<=200000

Input

Output

Sample Input

4 5
1 2 5
1 3 2
2 3 1
2 4 4
3 4 8

Sample Output

12

HINT


Source

[Submit][Status][Discuss]

HOME Back