← 返回题目
题库练习 大逃离
← 上一题 下一题 →

A2172 | 大逃离

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

这是一棵有n个节点的图，有m条双向边，每一条路有w个单位距离，zrz在1的位置，出口在n的位置，zrz想走第2短的路，第2短路径允许与最短路径有重边，然后也可以重复通过一些节点和路，注意如果有多条路径都是最短路径，那么他们都不能叫第2短路径。但是zrz觉得如果接下来进入的一个节点所直接连接的地方小于k个（起点和终点除外），那么他就不敢进去。

输入格式

第一行3个数：n,m,k

接下来m行：每行3个数，u，v，w。表示从u到v有一条权值为w的边。（u,v<=n，w<=10000）

输出格式

一个数：表示从s走到t的第2短路的值，如果不存在，输出-1

输入输出样例

输入 #1
4 4 1
1 2 100
2 4 200
2 3 250
3 4 100
输出 #1
450
输入 #2
4 4 3
1 2 100
2 4 200
2 3 250
3 4 100
输出 #2
500
C++ 编辑器
输入
输出