A7170 | $雾港城的道路网$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港城的道路网是一张无向带权图。每个路口 $i$ 都有一个“标高” $h[i]$。 你要从起点 $S$ 走到终点 $T$，路径的总代价为经过道路长度之和。 但夜里巡逻有规定：一路上标高只能 先不下降、再不上升 （允许相等）。 也就是说，存在某个位置（可以在起点或终点），使得整条路径的标高序列满足： * 前半段：标高单调不下降； * 后半段：标高单调不上升； 中途只允许发生一次“从上升到下降”的大转折（不转折也算合法）。 请你求出满足规定的最短路长度；若不存在合法路径输出 $-1$。

第一行四个整数 $n,m,S,T$，表示点数、边数、起点、终点。 第二行 $n$ 个整数 $h[1],h[2],\dots,h[n]$。 接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条无向边 $(u,v)$，边权为 $w$。

输出一个整数，表示最短合法路径长度；若无解输出 $-1$。

输入 #1

6 6 1 6
1 3 5 4 2 1
1 2 2
2 3 2
3 4 2
4 5 2
5 6 2
2 5 1

输出 #1

样例解释 解释：若直接走 1-2-5-6，标高为 1,3,2,1，中间先上升再下降，合法，代价为 $2+1+2=5$。 而 1-2-3-4-5-6 的标高 1,3,5,4,2,1 也是“先不降后不上”，代价更大。 所以答案为 $5$。 数据范围与测试点 * $1\le n\le200000$ * $0\le m\le200000$ * $1\le w\le10^9$ * $1\le h[i]\le10^9$ 测试点编号$n$ 上界$1\sim4$$n\le20$$5\sim10$$n\le10000$$11\sim20$$n\le200000$

C++ 编辑器

输入

输出