6137. 不同的路径 II (Distinct Routes II)
时间限制：1000 MS 内存限制：512 MB
题目描述
## 题目描述 某游戏包含 $n$ 个房间和 $m$ 个单向传送门。在每一天的开始，你从 $1$ 号房间出发，必须到达 $n$ 号房间。 在整个游戏游玩过程中，每个传送门最多只能使用一次。你希望连续玩这个游戏恰好 $k$ 天。每次使用传送门，你都需要支付 $1$ 枚金币。如果采取最优策略，在 $k$ 天内你所需支付的最小金币总数是多少？ ## 输入格式 第一行包含三个整数 $n, m$ 和 $k$，分别表示房间数量、传送门数量以及游玩天数。房间编号为 $1, 2, \dots, n$。 接下来 $m$ 行描述传送门。每行包含两个整数 $a$ 和 $b$，表示存在一条从房间 $a$ 指向房间 $b$ 的传送门。不存在两个起点和终点完全相同的传送门。 ## 输出格式 第一行输出一个整数，表示最优策略下所需支付的最小金币数。 随后，依次输出 $k$ 条路径的描述（格式参见样例，每行首先输出路径中房间的数量，随后输出路径经过的房间编号）。你可以输出任意一种合法的解。 如果不可能连续游玩 $k$ 天，则仅输出 `-1`。 ## 输入输出样例 ### 输入 #1 ``` 8 10 2 1 2 1 3 2 5 2 4 3 5 3 6 4 8 5 8 6 7 7 8 ``` ### 输出 #1 ``` 6 4 1 2 4 8 4 1 3 5 8 ``` ## 说明/提示 ### 数据规模与约定 * $2 \le n \le 500$ * $1 \le m \le 1000$ * $1 \le k \le n-1$ * $1 \le a, b \le n$