TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

10.0% (1/10)

Description

每家西提(Megacity)的犯罪率越來越高了。為了打擊犯罪,當政者成立了公路巡守機制。

城市裡有許多單行道,在每條道路的終點都有巡守軍的基地,每座基地都有許多隻軍隊。

起初,每個基地都會對每一條連外道路派出一隻軍隊。該隻軍隊會巡守沿途走過的道路,直到抵達道路中點的另一座基地。

他會在那座基地等待,之後在那座基地等待最久的一隻軍隊會沿著最久沒再被巡邏過的道路巡邏,並前往下一座基地。

很快地,他們發現了一些問題。也就是一條道路被巡邏的次數越來越倚重於該基地連出去以及連進來的道路數量。

也就是說,如果連出去的道路比連進來的道路少,那連外道路被巡邏的機會也會較少。

尤有甚者,若有一座基地沒有任何道路連進來,那麼他的連外道路僅會被巡邏到一次。

以此,公路巡守決定不巡邏一些道路,使得每個基地巡邏出去和巡邏回來的道路數量要一樣,

沒有被巡邏的道路將要用監視攝影機來監管。

但是,因為某些安全顧慮,有些道路被規定一定要巡邏,也就是絕對不能裝監視錄影機。

現在,給每條道路巡邏的成本以及監視錄影的成本。找到掌控整個城市所需的最小花費。

但是記著,整個城市都靠監視錄影是不可行的。也就是整座城市至少要有一條道路是被巡邏的。

Input Format

第一行包含一個正整數T(T≤ 70)表示測資筆數。

接下來會有T筆測資,每筆由兩個數字N(1 ≤ N ≤ 100)、M(1 ≤ M ≤ 1000)開頭。

N表示基地個數(編號1~N)、M表示公路個數。

接下來有M行表示M條道路,每行有五個數字u,v,p,s,x(1 ≤ u,v ≤ N,0 ≤ p,s ≤ 1000000),

u是這條道路的起點、v是這條道路的終點、p表示巡邏(patrolling)成本、s表示監視成本(video surveillance)、

若x=1表示這條道路一定得被巡邏,反之x=0

Output Format

對每筆測資,先輸出Case Number,接下來:

輸出小監控整座城市的成本,

若不可能達到則輸出"impossible"(不含雙引號)。

詳細輸出請看範例。

Sample Input

2
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 0
4 5
1 2 10 25 0
2 3 10 5 0
3 1 10 5 0
2 4 10 5 0
4 3 30 5 1

Sample Output

Case 1: 40
Case 2: 65

Hints

Problem Source

原TIOJ1688 / ACM-ICPC Asia Phuket 2009 prob K, NTUJ 1021

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 65536 262144 1