题目描述

点此下载 2024 年实验室二面题解

在我的世界起床战争中有$n$座编号为$1,2,3,...,n$的岛屿以及$m$条路，第$i$条路连接着岛屿$u_{i}$和$v_{i}$，长度为$w_{i}$。你的速度为$s$(其初始化为0)，通过每条路的时间为$⌊w_{i}/(s+1)⌋$，幸运的是地图上共有$k$瓶药水且每座岛屿都至多存在一瓶药水，若你此时所在的岛屿存在药水，你可以选择喝下该药水，每瓶药水喝完就会立即消失。这些药水有$2$个等级(I级或II级)，假设喝之前你的速度为$i$,当你喝下等级为$j$的药水后：

- 若$i>j,$你的速度将不会变化。
- 若$i=j,$你的速度将迅速+1。
- 若$i<j,$你的速度将迅速变为$j$。

你开始在1号岛屿上想要用最短时间去$n$号岛屿。

输入描述

第一行输入3个整数$n,m,k$(分别表示岛屿数，边数，药水数)$;$

接下来k行每行输入2个整数$a,b$($a$表示有药水的顶点，$b$表示该药水等级)$;$

随后m行分别输入3个整数$u_{i}，v_{i}，w_{i}$(表示第岛屿$u_{i}$和$v_{i}$之间有一条路，路长为$w_{i}$)。

保证不会出现自环和两点间多条边。

$2<=n<=100，1<=m<=4000，0<=k<=10，0<=a<=n，1<=b<=2，1<=u_{i},v_{i}<=n，10<=w_{i}<=1e5。$

输出描述

输出一个整数代表最少花费的时间，如果无法到达，请输出-1。

示例 1

输入

5 5 2
2 2
4 2
1 2 100
2 3 3000
1 4 100
3 4 3000
3 5 100

输出

941

说明

你的路线为$1$->$2$(此时速度变为$2$)->$1$->$4$(此时速度变为$3$)->$3$->$5$。可以验证这是最优解。