AdditionalFile4976.zip

P3597 [POI 2015 R3] 旅行 Trips

题目描述

给定一张 $n$ 个点 $m$ 条边的带权有向图，每条边的边权只可能是 $1$，$2$，$3$ 中的一种。

将所有可能的路径按路径长度排序，请输出第 $k$ 小的路径的长度，注意路径不一定是简单路径，即可以重复走同一个点。

输入格式

第一行包含三个整数 $n,m,k$（$1\le n\le 40$，$1\le m\le 1000$，$1\le k\le 10^{18}$）。

接下来 $m$ 行，每行三个整数 $u,v,c$（$1\leq u,v\leq n$，$u\neq v$，$1\le c\le 3$），表示从 $u$ 出发有一条到 $v$ 的单向边，边长为 $c$。

可能有重边。

输出格式

包含一行一个正整数，即第 $k$ 短的路径的长度，如果不存在，输出 $-1$。

输入输出样例 #1

输入 #1

6 6 11
1 2 1
2 3 2
3 4 2
4 5 1
5 3 1
4 6 3

输出 #1

4

说明/提示

【样例解释】

长度为 $1$ 的路径有 $1\to 2$，$5\to 3$，$4\to 5$。长度为 $2$ 的路径有 $2\to3$，$3\to4$，$4\to5\to3$。长度为 $3$ 的路径有 $4\to6$，$1\to2\to3$，$3\to4\to5$，$5\to3\to4$。长度为 $4$ 的路径有 $5\to3\to4\to5$。

原题名称：Wycieczki。

#4976. 「POI2015 R3」旅行 Trips

标签: 传统 | 时间限制: 19500 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXII Olimpiada Informatyczna — III etap Wycieczki

Bajtazar 迷上了自行车旅行的魅力，计划在字节城的 $k$ 天假期中，每天骑行一条不同的路线，挑战自我。他希望逐渐增加难度，每天的路线不短于前一天。具体来说，第 $i$ 天他想选择字节城中第 $i$ 短的可能路线。请你帮助 Bajtazar 计算第 $k$ 天旅行的路线长度。

字节城有 $n$ 座城市，编号 $1$ 到 $n$，通过单向道路连接，道路长度为 $1$、$2$ 或 $3$ 公里，可能经过隧道或高架桥。旅行路线可在任意城市起止，可多次经过同一城市或道路。

输入格式

第一行包含三个整数 $n, m, k$ $(1 \leq n \leq 40, 1 \leq m \leq 1000, 1 \leq k \leq 10^{18})$，分别表示城市数、道路数和假期天数。

接下来的 $m$ 行描述道路，每行包含三个整数 $u, v, c$ $(1 \leq u, v \leq n, u \neq v, 1 \leq c \leq 3)$，表示从 $u$ 号城市到 $v$ 号城市的单向道路，长度 $c$ 公里。两城市间可能有多条道路。

输出格式

输出一行，一个整数，表示第 $k$ 短旅行的长度。若可行旅行少于 $k$ 条（Bajtazar 需提前结束假期），输出 $-1$。

样例

输入

6 6 11
1 2 1
2 3 2
3 4 2
4 5 1
5 3 1
4 6 3

输出

4

• 长度 $1$ 的旅行：$1 \rightarrow 2$，$5 \rightarrow 3$，$4 \rightarrow 5$。
• 长度 $2$ 的旅行：$2 \rightarrow 3$，$3 \rightarrow 4$，$4 \rightarrow 5 \rightarrow 3$。
• 长度 $3$ 的旅行：$4 \rightarrow 6$，$1 \rightarrow 2 \rightarrow 3$，$3 \rightarrow 4 \rightarrow 5$，$5 \rightarrow 3 \rightarrow 4$。
  第 $11$ 短旅行（长度 $4$）例如为：$5 \rightarrow 3 \rightarrow 4 \rightarrow 5$。

附加样例

1. $n=10, k=46$，道路长度随机，形成链状网络，仅有 $45$ 条可行旅行，答案为 $-1$；
2. $n=15, k=10^{12}$，每对城市间有长度 $3$ 的道路。

数据范围与提示

对于 $25\%$ 的数据，$k \leq 1000000$。
对于 $50\%$ 的数据，每条道路 $c=1$。
对于 $75\%$ 的数据，$n \leq 15, m \leq 200, k \leq 10^{12}$。