CSES2130 不同路径 II
#CS2130. 不同路径 II
不同路径 II
题目背景
翻译自 CSES-2130 题。
题目描述
一个游戏包含了n个房间和m个传送门。每天游戏开始时，你从房间1出发，目标是到达房间n。
你在游戏中每个传送门最多只能使用一次。你希望在游戏中玩k天，每次使用任何传送门都需要支付一个金币。问题是，在最优的情况下，k天内你需要支付的最少金币数是多少？
输入格式
第一行包含三个整数n、m、k，分别表示房间的数量、传送门的数量以及你玩游戏的天数。房间编号从1到n。
接下来的m行中，每行描述一个传送门，包含两个整数a和b，表示有一个传送门可以从房间a到房间b。
输出格式
首先输出一个整数，表示在最优情况下，你需要支付的最少金币数。
然后，输出k条路径描述，按照示例格式。你可以输出任意一个有效的路径方案。
如果无法在k天内完成游戏，输出−1-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
6
4
1 2 4 8
4
1 3 5 8
说明/提示