企鹅国的最短路径问题

题目描述

在北纬 91°，有一个神奇的国度叫做企鹅国。这里的企鹅拥有发达的企鹅文明，由于企鹅只有黑白两种颜色，他们的数学体系以二进制为基础发展而来。

早在 $11101001_2$（十进制 233）年前，企鹅们就掌握了异或（$\oplus$）的数学概念。异或运算规则为“相同取 0，相异取 1”，即两个二进制位若不同则结果为 1，若相同则结果为 0，也可看作不带进位的二进制加法。

而在 $1000010_2$（十进制 66）年前，企鹅国的大科学家 Penguin. Tu 就提出了图与最短路径的概念——即在由顶点和边组成的图中，寻找从起点到终点、累计代价最小的路线。

企鹅国中有 $N$ 座城市，编号从 1 到 $N$。城市间的通行方式有两种：

1. 普通路径：任意两座城市 $i$ 和 $j$ 之间可直接通行，花费时间为 $(i \oplus j) \times C$（$C$ 为给定常数）。
2. 快捷通道：存在 $M$ 条单向快捷通道，第 $i$ 条通道从城市 $F_i$ 通向城市 $T_i$，通过需消耗 $V_i$ 的时间。

现在，来自 Penguin Kingdom University 的企鹅豆豆想从城市 $A$ 前往城市 $B$，请你计算最少需要多少时间。

输入格式

从标准输入读入数据：

• 第一行包含三个整数 $N$、$M$、$C$，分别表示城市个数、快捷通道个数、普通路径的时间系数。
• 接下来 $M$ 行，每行三个正整数 $F_i$、$T_i$、$V_i$，满足 $1 \leq F_i \leq N$、$1 \leq T_i \leq N$、$1 \leq V_i \leq 100$，分别表示快捷通道的起点、终点和消耗时间。
• 最后一行包含两个正整数 $A$、$B$，满足 $1 \leq A, B \leq N$，表示起点城市和终点城市。

输出格式

输出到标准输出：

• 一行一个整数，表示从城市 $A$ 到城市 $B$ 的最少通行时间。

样例

样例 1

输入

4 2 1
1 3 1
2 4 4
1 4

输出

5

解释

直接选择普通路径从 1 走到 4，花费时间为 $(1 \oplus 4) \times 1 = 5 \times 1 = 5$，是最优方案。

样例 2

输入

7 2 10
1 3 1
2 4 4
3 6

输出

34

解释

最优路径为：3 → 2（普通路径，花费 $(3 \oplus 2) \times 10 = 1 \times 10 = 10$）→ 4（快捷通道，花费 4）→ 6（普通路径，花费 $(4 \oplus 6) \times 10 = 2 \times 10 = 20$），总时间 $10 + 4 + 20 = 34$。

数据范围与提示

子任务编号	$N$ 的取值	$M$ 的取值	子任务分值
1	$= 10^5$	$= 0$	1
2	$= 1$	无限制	2
3	$= 3$		4
4	$= 10$		8
5	$= 10^3$		15
6		$\leq 5 \times 10^5$
7	$= 10^5$	无限制	55

提示：本题的核心是处理“无限普通路径 + 有限快捷通道”的图模型，需结合异或的性质优化最短路径算法，避免直接枚举所有普通路径。