2132: 最短路

题目描述


在北纬91o,有一个神奇的国度,叫做企鹅国。这里的企鹅也有自己发达的文明,称为企鹅文明。因为企鹅只有黑白两种颜色,所以他们的数学也是以二进制为基础发展的。
比如早在11101001年前,他们就有了异或这样一个数学概念。如果你不知道异或是什么,请出门过墙左转到这里。
再比如早在1000010年前,他们的大科学家 Penguin. Tu 就提出了图和最短路径这样一些概念。


企鹅国中有N座城市,编号从1到N 。
对于任意的两座城市i和j,企鹅们可以花费(i XOR j) *c的时间从城市i走到城市j,这里 为一个给定的常数C。
当然除此之外还有M条单向的快捷通道,第 i条快捷通道从第Fi个城市通向第 Ti个城市,走这条通道需要消耗 Vi的时间。
现在来自 Penguin Kingdom University 的企鹅豆豆正在考虑从城市A 前往城市B最少需要多少时间?

输入


从标准输入读入数据。
输入第一行包含三个整数NMC,表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数C。
接下来的 M行,每行三个正整数Fi,Ti,Vi(1<=Fi,Ti<=N ,1<=Vi<=100) ,分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。
最后一行两个正整数 A B(<=100),表示企鹅豆豆选择的起点城市标号和终点城市标号。

输出


输出到标准输出。
输出一行一个整数,表示从城市A前往城市B需要的最少时间。

样例输入


【样例输入1】
4 2 1
1 3 1
2 4 4
1 4
【样例输入2】
7 2 10
1 3 1
2 4 4
3 6

样例输出


【样例输出1】
5
【样例输出2】
34

提示


样例解释 1
直接从 1走到4就好了。


样例解释 2
先从3走到2,再从2通过通道到达4 ,4再从6走到 。
数据范围与提示
N<=10^5 M<=5*10^5
子任务编号 子任务分值
活泼可爱的出题人给大家留下了下面这张图。

来源/分类



请先 登录 后评论
  • 0 关注
  • 0 收藏,418 浏览
  • 轩爸 提出于 2019-08-02 22:38

相似问题