TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

68.8% (11/16)

Submission's AC Ratio

16.3% (16/98)

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

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

Sample Output

80
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 131072 65536 1 5 7 8
1 2500 131072 65536 2 4 6 8
2 2500 131072 65536 2 4 6 8
3 2500 131072 65536 2 4 6 8
4 2500 131072 65536 5 6 7 8
5 2500 131072 65536 3 4 7 8
6 2500 131072 65536 3 4 7 8
7 2500 131072 65536 3 4 7 8
8 2500 131072 65536 4 8
9 2500 131072 65536 4 8
10 2500 131072 65536 5 7 8
11 2500 131072 65536 5 7 8
12 2500 131072 65536 5 7 8
13 2500 131072 65536 6 8
14 2500 131072 65536 6 8
15 2500 131072 65536 7 8
16 2500 131072 65536 7 8
17 2500 131072 65536 8
18 2500 131072 65536 8