Traveling Politician
Time Limit: 2 seconds
一位來自 Alliance of Conservative Monarchists (ACM) 的政治家將成為下一次選舉的候選人，為了確保他能勝選，他將會舉行至少 k (≧ k)場公開演講。他將會在每一天都舉行演講，但不會連續兩天都在同一個城市中舉行演說，因為這麼做是徒勞無用的。然而，這位政治家相信間隔一天之後的演講是有用的，例如他在星期一演講過，而星期三他也許會在同一個城市中演講，人們將會忘記他第一次演講的內容，而第二次的演講就會更有效用。
他非常堅信會贏得這場勝利，因此他將會移動到首都。他的第一場演講來自於他的家鄉，而最後一場演講將會在首都。演講太多次將會使他疲累，因此不希望舉行太多場，但至少舉行 k 場以贏得勝利。
找一個最少的演講次數，從起點家鄉到終點首都至少舉行 k 場演講 (包括在家鄉跟首都的演講)，同時也不會存在連續兩天在同一個城市演講。
Input
輸入將會包含少數幾筆冊資，每組測資將會有 3 個整數，分別是 n, m, k 代表接下來有 n 個城市、m 條道路及舉行至少 k 場演講。接下來會有 m 行，每行會有 2 個整數 u, v，表示政治家可從城市 u 抵達城市 v (需要一天的時間)，而其他的路線因為他的經費不夠無法使用。而起點家鄉編號 0，終點首都編號 n-1。
輸入將會包含少數幾筆冊資，每組測資將會有 3 個整數，分別是 n, m, k 代表接下來有 n 個城市、m 條道路及舉行至少 k 場演講。接下來會有 m 行，每行會有 2 個整數 u, v，表示政治家可從城市 u 抵達城市 v (需要一天的時間)，而其他的路線因為他的經費不夠無法使用。而起點家鄉編號 0，終點首都編號 n-1。
2<=n<=50, 2<=k<=16
最後一行以包含兩個 0 結束程序
Output
對於每組測資輸出一行最少的演講個數，如果沒辦法則輸出 "LOSER"。
如果舉行大於 20 場，同樣也輸出 "LOSER"。
對於每組測資輸出一行最少的演講個數，如果沒辦法則輸出 "LOSER"。
如果舉行大於 20 場，同樣也輸出 "LOSER"。
| Sample Input | Sample Output |
3 3 3 0 1 0 2 1 2 5 6 5 0 1 0 3 1 2 2 4 3 2 3 4 3 3 10 0 1 1 0 1 2 0 0 0 |
3 LOSER 11 |
Problemsetter: Igor Naverniouk, special thanks to Shahriar Manzoor
沒有留言:
張貼留言