2171 . 打卡遊戲 (Checkin)
TopCoder
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
1 1 5
1 2 4
1 3 8
2 1 4
2 2 4
Sample Output 1
Sample Input 2
1 1 5
1 2 4
3 3 8
2 1 4
2 2 4
Sample Output 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 分。
對於所有測資，保證 $1 \le S, M \le 10 ^ 9$
Problem Source
108 北市賽 pC
testdata set by Omelet
2021.07.09 Update: 修補測資範圍 by FHVirus
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 |