P6581: 道路障碍
传统题
1.000s
时间限制
128MB
内存限制
3 提交
2 解决
【题目描述】
贝西搬到了一个小农场，有时候，她会回来看看她的朋友们。由于路上风景不错，她不想走得太快于是贝西决定不走最短路径，而是走次短（即第二短）的路径（假定次短路径一定是存在的）。
村里一共有R (1 ≤ R ≤ 100000)条双向道路，N (1 ≤ N ≤ 5000)个结点（从1到N编号）。
贝西的起点是1号点，目的地（就是她朋友的家）在N号点。
次短路径的有些边可以和最短路径重复，而且也允许存在圈，即次短路径上允许重复多次通过一些点或边。我们要求次短路径要严格大于最短路径。比如说，如果有两条不同的路径都是最短路径，那么他们都不能算是次短路径，次短路径一定要比它们长。
【输入】
第一行：两个用空格分开的整数：N和R
第二行到R + 1行：每一行有三个整数：A，B和D，表示一条道路连接了A点和B点，长度为D (1 ≤ D ≤ 5000)
【输出】
单独一行：从1号点到N号点的第二短的路径。
【样例输入】复制
4 4
1 2 100
2 4 200
2 3 250
3 4 100
【提示】
【hint】
（最优路线：1 2 4，长度为100 + 200 =300；次优路线 1 2 3 4，长度为100 + 250 + 100 = 450）