352 . 次短距離
TopCoder
Description
歹丸國的新總統正在重新擘畫歹丸國的城市規劃，其中最重要的問題就是城市間的交通。歹丸國的城市之間均以單行道相連，此外因為歹丸國奇特的地理環境，城市間的單行道長度也十分不一。新總統為了展現堅定的改革意志，決定先注資新台幣6894744元開發新軟體，重新根據各單行道的長度，來計算兩兩城市之間的最短距離，希望多少能再短一些，就可以當成政績了！
廠商經過隨意一番研究，發現大事不妙，原先的數據竟然都已經是最短距離了！！！於是廠商只好偷偷在軟體裡面動手腳，使得原本要計算從城市 $i$ 到城市 $j$ 的最短距離，該軟體將會輸出次短距離（不能再更長了，不然會被發現，達成次短距離的路徑可以經過重複的點或邊），這個距離一定要超過城市 $i$ 到城市 $j$ 的最短距離，如此一來才不會有抄數據的嫌疑！
你很好奇對於兩個城市而言，次短距離比最短距離長了多少。對了，由於交接失誤，此處單行道的長度有可能是負數，因此最短距離與次短距離均有可能是零或是負數。
Input Format
第一行為一個正整數$N$，表示城市的個數。
接著有 $N$ 列，其中第 $i$ 列有 $N$ 個整數 $c_{i1},c_{i2}, \ldots ,c_{iN}$ 。其中 $c_{ij}$ 代表歹丸國的從城市 $i$ 到城市 $j$ 的單行道長度。（輸入保證對角線上為 $0$ ）
- $2\leq N \leq 500$
- $\forall i$, $c_{ii} = 0$
- $\forall i \neq j$, $-2000000\leq c_{ij} \leq 2000000$
- 保證任兩城市之間的最短距離、次短距離存在且為有限值。
Output Format
請輸出 $N$ 列，其中第 $i$ 列有 $N$ 個正整數 $e_{i1} - d_{i1},\;\;e_{i2} - d_{i2},\;\;\ldots ,\;\;e_{iN} - d_{iN}$（以空白隔開，即行末無空白）。對所有$i \neq j$，其中 $e_{ij}$ 代表廠商所輸出從城市 $i$ 到城市 $j$ 的次短距離、$d_{ij}$ 代表實際上從城市 $i$ 到城市 $j$ 的最短距離；對所有$i=j$，$d_{ij}=e_{ij}=0$。
Sample Input 1
0 3
4 0
Sample Output 1
7 0
Sample Input 2
0 5 7
-1 0 9
-2 8 0
Sample Output 2
4 0 3
4 4 0
Hints
範例一說明：$d_{1,2}=3,\;d_{2,1}=4,\;e_{1,2}=10,\;e_{2,1}=11,\;d_{1,1}=d_{2,2}=e_{1,1}=e_{2,2}=0$
Problem Source
NEOJ Problem 395
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1, 8~11 | $N \leq 20$ | 20 |
| 2 | 2~4 | $N \leq 100$ | 40 |
| 3 | 5~7 | 無額外限制 | 40 |