給一張
定義「交替路徑」為
也就是對於一條交替路徑
求全點對最短「交替路徑」長。
第一行有一個整數
對與每一筆測資:
第一行有兩個整數
接下來有
代表第
對於所有測資,保證
且對於所有
保證
對於每一筆測資,輸出一個整數
其中
特別的,定義
範例測資的 dis[i][j]
如下(不存在表示為 -1
):
Case #1
0 1 2 2 3
1 0 1 1 2
2 1 0 1 -1
2 1 1 0 1
3 2 -1 1 0
Case #2
0 215 121 46 65 56 4
215 0 172 97 116 170 55
121 172 0 145 22 85 103
46 97 145 0 19 60 42
65 116 22 19 0 63 61
56 170 85 60 63 0 18
4 55 103 42 61 18 0
Case #3
0 28 33 16 6 81 -1 46
28 0 51 100 22 99 -1 74
33 51 0 39 29 48 -1 79
16 100 39 0 10 87 -1 62
6 22 29 10 0 77 -1 52
81 99 48 87 77 0 -1 127
-1 -1 -1 -1 -1 -1 0 -1
46 74 79 62 52 127 -1 0
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0 | 範例測資 | 0 |
2 | 1~3 | 對於所有 |
6 |
3 | 5~7 | 7 | |
4 | 1~3, 5~9 | 對於所有 |
10 |
5 | 0, 4, 10~12 | 15 | |
6 | 1~4, 13~14 | 對於所有 |
11 |
7 | 0, 4~7, 10~12, 15~16 | 12 | |
8 | 0~18 | 無額外限制 | 39 |