J13 习题-4 Nya图中的最短路径

题目描述

这是一个非常简单的问题，你的任务只是计算图形中的最短路径，只需稍微修改一下算法。如果你不明白这段话，就继续说。

NYA图是一个有“层”的无向图。图中的每个节点属于一个层，总共有 $n$ 个节点。

您可以使用成本 $C$ 从 $X$ 层的任何节点移动到 $X+1$ 层的任何节点，因为道路是双向的，因此也允许以相同的成本从 $X+1$ 层移动到 $X$ 层。

此外，还有 $M$ 个额外的边，每个边连接一对节点 $U$ 和 $V$，代价是 $W$。

帮助我们计算从节点 $1$ 到节点 $N$ 的最短路径。

输入格式

第一行有一个数字 $T$（$T \le 20$），表示测试用例的数量。

对于每个测试用例，第一行有三个数字 $N$、$M$和 $C$，这是节点数、额外边数和相邻层之间移动的成本。

第二行有 $N$ 个数字 $l_i$（$1\le l_i\le N$），这是第 $i$ 个节点所属的层。

然后是 $M$ 条线，每条线有 $3$ 个数字，$u,v$（$1\le u,v\le N$，$u \neq v$）和 $w$，这意味着有一条额外的边，连接一对节点 $u$ 和 $v$，成本为 $w$。

输出格式

对于测试用例 $X$，首先输出“case#X:”，然后输出从节点 $1$ 移动到节点 $N$ 的最小成本。

如果没有解决方案，则输出-1。

输入样例

2
3 3 3
1 3 2
1 2 1
2 3 1
1 3 3

3 3 3
1 3 2
1 2 2
2 3 2
1 3 4

输出样例

Case #1: 2
Case #2: 3

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据： $0 \le N,M \le 10^5$， $1\le C\le 10^3$，$1\le w\le 10^4$。