Distinct Routes II

题目描述

一个游戏由 $n$ 个房间和 $m$ 个传送器组成。在每天开始时，你从房间 1 出发，需要到达房间 $n$。 在整个游戏过程中，每个传送器最多可以使用一次。你想玩恰好 $k$ 天。每次使用任意传送器都要付出一枚硬币。如果你最优地游玩，恰好玩 $k$ 天时最少需要付出多少枚硬币？

输入格式

第一行输入包含三个整数 $n, m$ 和 $k$：房间数、传送器数以及你玩游戏的天数。房间编号为 $1,2,\dots,n$。 随后有 $m$ 行描述传送器。每行包含两个整数 $a$ 和 $b$：存在一条从房间 $a$ 到房间 $b$ 的传送器。 不存在起点和终点都相同的两条传送器。

输出格式

首先输出一个整数：如果你最优地游玩，恰好玩 $k$ 天时最少需要付出的硬币数。然后按示例输出 $k$ 条路线描述。你可以输出任意一个合法解。 如果无法恰好玩 $k$ 天，则只输出 -1。

8 10 2
1 2
1 3
2 5
2 4
3 5 
3 6
4 8
5 8
6 7 
7 8

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$

标签: CSES2130|先进技术

来源

CSES2130|先进技术