TopCoder

Thumb fhvirus icon.001
FHVirus
"FHVirus 是一種由主要由IO組合而成的病毒。"

User's AC Ratio

96.2% (25/26)

Submission's AC Ratio

30.6% (37/121)

Description

知名的電視節目「Jumping Kid」即將在台北市舉辦一場大規模的打卡遊戲,在這個遊戲中,每個參賽隊伍會收到相同的 $K$ 個任務,每個任務包含一個夜市景點和一個公園景點,解決任務的方法,則是需要以計程車為交通工具,在該任務的兩個景點(不限定順序)完成打卡,而每次的計程車車資為起跳金額 $S$ 元,加上每公里 $M$ 元(假設計程車皆走最短路徑,且雙向的路徑長度相同)。

參賽隊伍可以選擇任一景點做為打卡遊戲的出發地點,為了節目效果,每個參賽隊伍一次只能執行一個任務,並不允許同時執行兩個(含)以上的任務,且每個任務也僅能執行一次。同時,為了節省車資,當任務的終點恰好是下一個任務的起點時,節目單位允許參賽隊伍可以連續打卡,以避免因為換車所需要多付的起跳金額 $S$ 元。另外,若任務的終點與下一個任務的起點不相同時,主辦單位會提供免費專車將參賽隊伍運送到下一個任務的起點,但參賽隊伍在抵達後,必須自行換乘計程車繼續解決任務,並且自付所需的車資。

您現在是這項遊戲的參賽者之一,請您根據主辦單位公佈的 $K$ 個任務,規劃可以用最少車資完成遊戲的方法,並且輸出您總共搭乘的計程車數量(假設每次叫車時,都搭乘到不一樣的車子)。

Input Format

輸入的第一行有五個以一個空白符號隔開的正整數 $A, B, S, M, K$,代表在這次的遊戲中,總共有可能出現 $A$ 個夜市景點和 $B$ 個公園景點,同時計程車車資的起跳金額為 $S$ 元,之後每公里要另外付 $M$ 元,並且總共會有 $K$ 個任務。接著 $K$ 行中,每一行有 $3$ 個空白符號隔開的正整數 $a, b, m$,代表一個任務中需要到第 $a$ 個夜市景點和第 $b$ 個公園景點打卡,同時兩個景點之間的距離為 $m$。注意,在遊戲中,兩個景點的打卡順序並無限制,同時每個任務都不會重複。

Output Format

請根據輸入的資料,輸出可以用最少車資完成遊戲所需搭乘的計程車數量。

Sample Input

輸入範例 1
2 3 100 20 5
1 1 5
1 2 4
1 3 8
2 1 4
2 2 4

輸入範例 2
3 3 100 20 5
1 1 5
1 2 4
3 3 8
2 1 4
2 2 4

Sample Output

輸出範例 1
1

輸出範例 2
2

Hints

範測 1 說明:一台計程車,從夜市 1 前往公園 1(任務一),再前往夜市 2(任務四),再前往公園2(任務五),再前往夜市 1(任務二),再前往公園 3(任務三)。

範測 2 說明:第一台計程車從夜市 1 前往公園 1,再前往夜市 2,再前往公園 2,再前往夜市1,完成任務一、四、五、二。搭主辦單位專車前往夜市 3,搭第二台計程車前往公園 3(任務三)。

本題共有四組測試資料,每組可有多筆測試資料:
第一組測試資料 $A = B = 2,0 < K \leq 4$,共 15 分;
第二組測試資料 $2 < A, B \leq 5,0 < K \leq 25$,共 25 分;
第三組測試資料 $5 < A, B \leq 100,0 < K \leq 10000$,共 29 分;
第四組測試資料 $100 < A, B \leq 500,0 < K \leq 250000$,共 31 分。

Problem Source

108 北市賽 pC
testdata set by Omelet

Subtasks

No. Testdata Range Constraints Score
1 0~4 $A = B = 2,0 < K \leq 4$ 15
2 5~29 $2 < A, B \leq 5,0 < K \leq 25$ 25
3 30~34 $5 < A, B \leq 100,0 < K \leq 10000$ 29
4 35~39 $100 < A, B \leq 500,0 < K \leq 250000$ 31

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1
1 1000 262144 65536 1
2 1000 262144 65536 1
3 1000 262144 65536 1
4 1000 262144 65536 1
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 3
31 1000 262144 65536 3
32 1000 262144 65536 3
33 1000 262144 65536 3
34 1000 262144 65536 3
35 1000 262144 65536 4
36 1000 262144 65536 4
37 1000 262144 65536 4
38 1000 262144 65536 4
39 1000 262144 65536 4