1016 . 過場動畫
TopCoder
Tags
Description
你還記得前幾道題目中的水果賽車嗎？現在小方塊正在使用另一種方式享受這個遊戲：全賽道速通！
在這個遊戲中，賽道被安排在一個 $n \times m$ 的表格上，每一個格子是一個賽道，也就是說，對於所有 $1 \leq i \leq n$ 與 $1 \leq j \leq m$ 都有一個賽道 $(i, j)$。全賽道速通顧名思義，就是在最少的時間內遊玩每個賽道至少一遍。不過，在這個遊戲中，不僅僅是遊玩賽道會花費時間：小方塊發現在連續遊玩兩個相近的賽道時，遊戲就會播放玩家從一個賽道開到另一個的過場動畫，不僅對速通玩家來說相當無聊，還耗費了大量的時間。
因此，在嘗試速通遊戲時，遊玩賽道的順序會對結果產生重大的影響！
除了練習賽車技術以外，小方塊同時也想知道遊戲的各種機制。
經過實驗後，他發現這個遊戲的過場動畫有 $k$ 種，每一種過場動畫都有三個參數 $\Delta x_i, \Delta y_i, t_i$，
這種過場動畫會在從任意賽道 $(x, y)$ 移動到 $(x + \Delta x_i, y + \Delta y_i)$ 的時候播放，無論起始或終點的賽道是什麼，都會花上 $t_i$ 單位的時間。
小方塊想要在每個賽道都遊玩恰好一次的前提下最小化觀看過場動畫的時間，因為遊玩賽道還是最耗費時間的部份。你能幫他找到這樣的一條路線嗎？
Input Format
輸入的第一行有兩個正整數 $n, m$ 代表表格的長寬。輸入的第二行只有一個整數 $k$，代表過場動畫的種類數。
接下來有 $k$ 行，第 $i$ 行中有三個整數 $\Delta x_i, \Delta y_i, t_i$。
- $1 \leq n, m \leq 1000$
- $0 \leq k \leq 24$
- $0 \leq |\Delta x_i|, |\Delta y_i| \leq 2$
- $1 \leq t_i \leq 10 ^ 8$
- 所有 $(\Delta x_i, \Delta y_i)$ 都兩兩相異且不是 $(0, 0)$。
Output Format
第一行請輸出一個整數表示所有路線中觀看過場動畫時間的最小值。
第二行請依序輸出 $2 \times n \times m$ 個整數 $x_1, y_1, x_2, y_2 \ldots, x_{nm}, y_{nm}$，代表其中一條達到最小值的路線是按照 $(x_1, y_1), (x_2, y_2), \ldots (x_{nm}, y_{nm})$ 的順序遊玩。
Sample Input 1
5 2 1 1 0 10
Sample Output 1
0 5 2 5 1 4 2 4 1 3 2 3 1 2 2 2 1 1 2 1 1
Sample Input 2
2 2 4 0 1 10 1 0 20 -1 0 30 0 -1 40
Sample Output 2
10 1 2 2 1 2 2 1 1
Sample Input 3
4 1 4 -2 0 30 -1 0 50 1 0 70 2 0 40
Sample Output 3
60 3 1 1 1 4 1 2 1
Sample Input 4
2 3 7 1 0 100 -1 -1 10 0 -1 100 1 -1 100 -1 1 100 0 1 100 1 1 100
Sample Output 4
20 2 2 1 1 1 3 2 1 2 3 1 2
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|