P15703 [2018 KAIST RUN Spring] Xtreme NP-hard Problem?!

*注意！* 本题已被证明是 NP 难问题。但由于规则并未禁止出 NP 难问题，我们决定保留此题。 有一个包含 $n$ 个顶点和 $m$ 条边的无向图。顶点和边的编号分别从 $1$ 到 $n$ 和从 $1$ 到 $m$，边 $i$ 的权重为 $w_i$（$1 \le i \le m$）。给定一个自然数 $k$，请找到一条从顶点 $1$ 开始、到顶点 $n$ 结束、且恰好包含 $k$ 条边的最短简单路径的长度。简单路径是指不重复经过同一顶点的路径，路径的长度是组成该路径的所有边的权重之和。

第一行包含三个由空格分隔的整数 $n$, $m$, $k$。 接下来的 $m$ 行，每行包含三个由空格分隔的整数 $x_i$, $y_i$, $w_i$。它们表示边 $i$ 连接顶点 $x_i$ 和顶点 $y_i$，且权重为 $w_i$。 输入中不包含自环或重边。

输出一条从顶点 $1$ 开始、到顶点 $n$ 结束、且恰好包含 $k$ 条边的最短简单路径的长度。如果不存在这样的路径，输出 $-1$。

### 数据范围 - $2 \le n < 10^6$ - $1 \le m, k < 10^6$ - $1 \le x_i, y_i \le n$ - $x_i \ne y_i$ ($1 \le i \le n$) - $i \ne j \Rightarrow \{x_i, y_i\} \ne \{x_j, y_j\}$ ($1 \le i, j \le n$) - $1 \le w_i \le 10^8$ - $\min(n,m,k)\le 5$ 翻译由 DeepSeek V3.2 完成