Skip to content

1047: 道路

题目

题目描述

有 $n$ 座城市,编号从 $1$ 到 $n$。

对于任意两座城市 $i$ 和 $j$,你可以花费 $(i \operatorname{xor} j)\times C$ 的时间从 $i$ 走到 $j$。这里的 $C$ 是一个给定的常数。

除此之外,还有 $M$ 条单向的道路,第 $i$ 条从第 $F_i$ 个城市通向第 $T_i$ 个城市,走这条路需要消耗 $V_i$ 的时间。

请输出从城市 $A$ 前往城市 $B$ 的最小用时。

输入格式

输入第一行包含三个整数 $n, m, C$ ,表示城市的个数、道路的条数以及题面中提到的给定的常数 $C$。

接下来的 $m$ 行,每行三个正整数 $F_i, T_i, V_i$ ,分别表示对应道路的起点城市标号、终点城市标号和通过这条道路需要消耗的时间。

最后一行两个正整数 $A, B$,表示起点城市标号和终点城市标号。

输出格式

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

样例输入

``` 7 2 10 1 3 1 2 4 4 3 6

```

样例输出

``` 34

```

数据范围

子任务编号 $n$ $m$ $C, V_i$ 子任务分值
$1$ $= 10 ^ 5$ $=0$ $\leq 100$ $1$
$2$ $=1$ $2$
$3$ $=3$ $4$
$4$ $=10$ $8$
$5$ $=10^3$ $15$
$6$ $=10^3$ $\leq 5 \times 10^5$
$7$ $=10^5$ $55$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!