CSES 2130 - Distinct Routes II

有一款遊戲由 \(n\) 個房間與 \(m\) 個傳送門組成。每天開始時你都位於房間 \(1\)，而你必須抵達房間 \(n\)。

整場遊戲中，每個傳送門至多只能使用一次。你想恰好玩 \(k\) 天這個遊戲。每使用一次傳送門，你就要付一枚金幣。如果你採取最佳策略，這 \(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

說明：第一個數字 \(6\) 是總金幣數。之後每條路徑先輸出這條路徑經過的房間數量，再輸出依序經過的房間編號。

限制

• \(2 \le n \le 500\)
• \(1 \le m \le 1000\)
• \(1 \le k \le n-1\)
• \(1 \le a, b \le n\)

題目來源

CSES - Distinct Routes II

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。