時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
Johnny 想從家出發，沿每條街道恰好行駛一次，最後回到家。街道是雙向的，行駛途中不能在同一條街上掉頭；街道可連接同一個路口，也可能有不同街道連接相同的兩個路口。 街道有互不相同的整數編號。若有多條符合條件的封閉路線，請輸出街道編號序列字典順序最小者：在第一個不同的位置，編號較小的序列較小。 Johnny 的家位於「輸入第一條街道的兩端路口中，編號較小的那個路口」。保證所有街道彼此可經由路口連通。
輸入格式
多個城市資料區塊。每行 x y z 表示編號 z 的街道連接路口 x 與 y；路口編號為 1 至 m，m ≤ 44；街道編號為 1 至 n，n < 1995。 每個區塊以一行 0 0 結束，該行沒有第三個整數。最後再以空區塊 0 0 結束整份輸入。
輸出格式
每個城市輸出兩行。第一行為所求街道編號序列，以空白分隔；無解時輸出 Round trip does not exist.。第二行為空白行，包括最後一筆。
題目來源：UVa 302 — John’s trip。 原題：https://onlinejudge.org/external/3/302.pdf
範例測資
範例輸入 1
1 2 1 2 3 2 3 1 6 1 2 5 2 3 3 3 1 4 0 0 1 2 1 2 3 2 1 3 3 2 4 4 0 0 0 0
範例輸出 1
1 2 3 5 4 6 Round trip does not exist.
請先登入後再提交程式碼
討論與題解
載入討論區…