#P4283. 魔法少女伊莉雅

    ID: 3501 传统题 1000ms 512MiB 尝试: 172 已通过: 27 难度: 8 上传者: 标签>难度分类提高+/省选-图论次短路Dijkstra维护多个距离状态贪心消除被支配候选CF2500

魔法少女伊莉雅

魔法少女伊莉雅

题目描述

士郎想从爱因兹贝伦城堡的房间 11 走到大厅 nn。城堡的通道是带正权的无向边。他不想走最短路,但希望在所有合法且严格比最短路长的路径中,选一条长度最小的。

合法路径不能经过重复的顶点。若某一条边能在某条从 11 到 nn 的最短路上沿 u→vu\to v 经过,士郎就不能沿 v→uv\to u 走这一条边。这个限制针对具体的边,存在重边时分别判断。最短路长度按原无向图计算。

输入格式

第一行两个整数 n,mn,m,表示顶点数和边数。接下来 mm 行,每行三个整数 u,v,wu,v,w,表示一条连接 u,vu,v、长度为 ww 的双向通道。

输出格式

输出一行一个整数,表示目标路径的最小长度。若不存在这样的路径,输出 -1。

样例 #1

样例输入 #1

2 2
1 2 1
1 2 2

样例输出 #1

2

样例说明

两条平行通道的长度分别为 11 和 22,最短路长度为 11,所以选长度为 22 的通道。

样例 #2

3 3
1 2 5
1 3 1
2 3 8
13

最短路是 1→31\to3,长度为 11;合法较长简单路径是 1→2→31\to2\to3,长度为 1313。绕回已经经过的节点不合法。

数据规模与约定

1≤n≤1051\le n\le10^5,1≤m≤5×1051\le m\le5\times10^5,1≤u,v≤n1\le u,v\le n,1≤w≤1031\le w\le10^3。