2204 . 交替路徑
TopCoder
Tags
Description
給一張 $n$ 點 $m$ 邊的簡單無向圖 $G$，每一條邊 $e_i$ 有兩個權重 $w_i, c_i$ ，前者代表長度，後者代表顏色。
定義「交替路徑」為 $G$ 上的一條路徑（不一定是簡單路徑），使得此路徑上沒有「連續」兩條邊有相同的顏色。
也就是對於一條交替路徑 $P = {e_1, e_2, \cdots, e_k}$，不存在 $1 \le i < k$ 使得 $e_i$ 和 $e_{i+1}$ 顏色相同。
求全點對最短「交替路徑」長。
Input Format
第一行有一個整數 $T$，代表有幾筆測資。
對與每一筆測資：
第一行有兩個整數 $n, m$，代表圖 $G$ 有 $n$ 點 $m$ 邊。
接下來有 $m$ 行，每行有四個整數 $u_i, v_i, w_i, c_i$，
代表第 $i$ 條邊 $e_i$ 連接 $u_i, v_i$，長度為 $w_i$，顏色為 $c_i$。
對於所有測資，保證 $n \le 500, m \le \frac{n(n-1)}{2}$，
且對於所有 $1 \le i \le m$，$1 \le u_i, v_i \le n, 1 \le w_i, c_i \le 10^ 9$
保證 $\sum {n} \le 2000$。
Output Format
對於每一筆測資，輸出一個整數 $H$，其中 $H = (\sum_{1 \le i < j \le n}{ (i + j) \cdot dis_{i, j}}) \mod (10^ 9 + 7)$
其中 $dis_{i, j}$ 代表 $i, j$ 的最短交替路徑。若不存在，則視為 $0$。
特別的，定義 $i, i$ 間最短交替路徑長度為 $0$。
Sample Input 1
3
5 5
1 2 1 1
2 3 1 2
3 4 1 1
4 2 1 2
4 5 1 1
7 10
1 6 56 1
1 7 4 1
2 7 55 1
3 5 22 1
4 5 19 1
4 6 73 1
4 7 42 3
5 6 63 3
5 7 95 3
6 7 18 1
8 7
1 3 33 1
1 5 6 2
1 8 46 4
2 5 22 1
3 5 29 4
3 6 48 2
4 5 10 1
5 5
1 2 1 1
2 3 1 2
3 4 1 1
4 2 1 2
4 5 1 1
7 10
1 6 56 1
1 7 4 1
2 7 55 1
3 5 22 1
4 5 19 1
4 6 73 1
4 7 42 3
5 6 63 3
5 7 95 3
6 7 18 1
8 7
1 3 33 1
1 5 6 2
1 8 46 4
2 5 22 1
3 5 29 4
3 6 48 2
4 5 10 1
Sample Output 1
80
12160
10665
12160
10665
Hints
範例測資的 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
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 1~3 | 對於所有 $1 \le i \le m$，$w_i = 1, c_i = i$ | 6 |
| 3 | 5~7 | $n \le 300$，且對於所有 $1 \le i \le m$，$c_i = i$ | 7 |
| 4 | 1~3, 5~9 | 對於所有 $1 \le i \le m$，$c_i = i$ | 10 |
| 5 | 0, 4, 10~12 | $n \le 100$，且對於所有 $1 \le i \le m$，$c_i \le 5$ | 15 |
| 6 | 1~4, 13~14 | 對於所有 $1 \le i \le m$，$w_i = 1$ | 11 |
| 7 | 0, 4~7, 10~12, 15~16 | $n \le 300$ | 12 |
| 8 | 0~18 | 無額外限制 | 39 |