华师一附中OI组

标题: P4366 [Code+#4]最短路 [打印本页]

作者: admin 时间: 2018-5-17 12:53
标题: P4366 [Code+#4]最短路
https://www.luogu.org/problemnew/show/P4366

题目描述
企鹅国中有 N 座城市，编号从 1 到 N 。对于任意的两座城市 i和 j ，企鹅们可以花费 (i xor j)×C 的时间从城市 i 走到城市 j ，这里 C 为一个给定的常数。

当然除此之外还有 M 条单向的快捷通道，第 i 条快捷通道从第 Fi个城市通向第 Ti 个城市，走这条通道需要消耗 Vi 的时间。

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

输入输出格式
输入格式：
从标准输入读入数据。

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

接下来的 M 行，每行三个正整数 Fi ,T,Vi（1≤Ti≤N,1≤Vi≤100 )，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。

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

输出格式：
输出到标准输出。

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

输入输出样例
输入样例#1：
4 2 1
1 3 1
2 4 4
1 4
输出样例#1：
5
输入样例#2：
7 2 10
1 3 1
2 4 4
3 6
输出样例#2：
34
说明
样例1解释

直接从 1 走到 4 就好了。

样例2解释

先从 3 走到 2 ，再从 2 通过通道到达 4 ，再从 4 走到 6 。

欢迎光临华师一附中OI组 (http://hsyit.cn/)