首页 > 试题广场 >

简单图论题

[编程题]简单图论题
\hspace{15pt}有一个 n 个点 m 条边构成的无向图 G，第 i 条边 (u_i,v_i) 有一个颜色 c_i。现在有一个环形颜色圆盘，其包含了编号 [0,P-1] 的颜色，圆盘上有一个指针，初始指向颜色 0，若指针指向颜色 x，则可以花费 1 的代价将其指向 \left(x+P-1\right)\bmod P 或 \left(x+1\right)\bmod P。
\hspace{15pt}第 i 个点有一个颜色偏转值 b_i。当你想走过边 (u,v,c) 时：
\hspace{23pt}\bullet\,若从点 u 走向点 v，那你在点 u 时圆盘的指针必须指向 \left(c+P-b_u\right)\bmod P，
\hspace{23pt}\bullet\,若从点 v 走向点 u，那你在点 v 时圆盘的指针必须指向 \left(c+P-b_v\right)\bmod P。
\hspace{15pt}注意，经过边时不能调整指针。

\hspace{15pt}求从点 1 到点 n 的最小代价，不可达输出 -1。

输入描述:
\hspace{15pt}第一行输入三个整数 n,m,P \left(1\le n,m\le 2\times 10^5;\, 1\le P\le 10^9\right)。
\hspace{15pt}第二行输入 n 个整数 b_1, b_2, \dots, b_n \left(0\le b_i<P\right)，表示第 i 个点的颜色偏转值。
\hspace{15pt}接下来 m 行，第 i 行输入三个整数 u_i,v_i,c_i \left(1\le u_i,v_i\le n;\, u_i\ne v_i;\, 0 \le c_i < P\right)，表示第 i 条边双向连接点 u_i 和点 v_i，颜色为 c_i。
\hspace{15pt}图可能不连通、可能存在重边。不存在自环。


输出描述:
\hspace{15pt}若点 1 无法到达点 n，输出 -1；否则，输出一个整数，表示从点 1 到点 n 的最小代价。
示例1

输入

5 7 20
10 7 10 16 15
1 2 3
2 3 2
1 4 13
4 5 10
3 4 1
2 5 19
1 5 19

输出

8

说明

\hspace{15pt}在这个样例中，初始图如下图所示，最优路线为 1\rightarrow 2\rightarrow 5。



示例2

输入

3 1 6
2 3 3
1 2 2

输出

-1
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 0浏览

热门推荐

相关试题

简单图论题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号