#P4366. [Code+#4] 最短路

    ID: 4580 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>图的建立,建图最短路进制

[Code+#4] 最短路

题目背景

在北纬 91° ,有一个神奇的国度,叫做企鹅国。这里的企鹅也有自己发达的文明,称为企鹅文明。因为企鹅只有黑白两种颜色,所以他们的数学也是以二进制为基础发展的。

比如早在 1110100111101001 年前,他们就有了异或这样一个数学概念。如果你不知道异或是什么,请出门过墙左转到这里

再比如早在 10000101000010 年前,他们的大科学家 Penguin. Tu 就提出了最短路径这样一些概念。

题目描述

企鹅国中有 NN 座城市,编号从 11NN

对于任意的两座城市 iijj ,企鹅们可以花费 (i xor j)×C(i~\mathrm{xor}~j) \times C 的时间从城市 ii 走到城市 jj ,这里 CC 为一个给定的常数。

当然除此之外还有 MM 条单向的快捷通道,第 ii 条快捷通道从第 FiF_i​​ 个城市通向第 TiT_i​​ 个城市,走这条通道需要消耗 ViV_i​​ 的时间。

现在来自 Penguin Kingdom University 的企鹅豆豆正在考虑从城市 AA 前往城市 BB 最少需要多少时间?

输入格式

从标准输入读入数据。

输入第一行包含三个整数 N,M,CN,M,C ,表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数CC

接下来的 MM 行,每行三个正整数 Fi,Ti,ViF_i,T_i,V_i​ (1FiN1 \leq F_i \leq N,1TiN,1Vi1001 \leq T_i \leq N ,1\leq V_i \leq 100),分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。

最后一行两个正整数 A,BA,B (1C100)(1 \leq C \leq 100),表示企鹅豆豆选择的起点城市标号和终点城市标号。

输出格式

输出到标准输出。

输出一行一个整数,表示从城市 AA 前往城市 BB 需要的最少时间。

4 2 1
1 3 1
2 4 4
1 4
5
7 2 10
1 3 1
2 4 4
3 6
34

提示

样例1解释

直接从 11 走到 44 就好了。

样例2解释

先从 33 走到 22 ,再从 22 通过通道到达 44 ,再从 44 走到 66

0

活泼可爱的出题人给大家留下了下面这张图。

1

Credit: https://www.luogu.org/discuss/show/38908