#131. 旅行! 我就是想去旅行!
旅行! 我就是想去旅行!
Time limit: 1 seconds
Memory limit: 512 megabytes
The thing that's between us is fascination, and the fascination resides in our being alike. Whether you're a man or a woman, the fascination resides in finding out that we're alike. —Practicalities, Writer, Marguerite Duras
题目描述
初入PKU晓神拿起了一本中国现代史饶有兴趣地阅读着, 她发现中国作为基建狂魔, 在交通建设方面飞速发展. 这时他又想Frank能从Fuzhou去Beijing找她玩. 于是她想到了如下问题:
中国大陆可以看作一个个点条路的无向图, 在这条路中,第条路都有一个初始长度, 由于中国交通飞速发展, 在第个时刻通过条道路的时间为我们认为如果Frank在时刻选择通过条路, 他可以在第时刻从消耗个单位时间到达. 在每个时刻, Frank可以选择一条路走, 或者停留在原地.
晓神希望Frank尽早去PKU找他玩, 于是她想请问聪明的你, Frank至少需要多少单位时间从Fuzhou(1号点)前往Beijing(N号点).
特别地: 我们认为Frank是从第1时刻开始行动的.
输入
第一行包含两个整数.
接下来行每行四个整数表示一条连接的无向边.
输出
输出一个整数表示Frank到达Beijing的最少时间.
限制
- .
- .
- .
- .
- 图保证联通且没有重边和自环.
2 1
1 2 2 3
4
2 3
1 2 2 3
1 2 2 1
1 1 1 1
3
6 9
1 1 0 0
1 3 1 2
1 5 2 3
5 2 16 5
2 6 1 10
3 4 3 4
3 5 3 10
5 6 1 100
4 2 0 110
20
Tips
For someone special: May your future travels, and the love of every hike, every look at the sea, every embrace in the landscape, can become each other's life, a flowing feast. Never go on trips with anyone you do not love.
Related
In following contests: