1164 . 喵喵的旅程
TopCoder
Description
有一天，喵喵想要去別的縣市玩，於是他選出了N個候選的縣市，從0編號到N-1。這些縣市都是由很多個鄉鎮構成，從0編號到M-1（M是該縣市的鄉鎮數量）。兩個不同的鄉鎮間可能會有一條雙向道路連接（總共K條道路，編號為0~K-1），但是任兩個鄉鎮間恰有唯一的路徑通行（可能經過別的鄉鎮）。每條道路的長度有可能不一樣，但是一定是正整數。
喵喵的時間不多，他只想要從其中挑出兩個縣市前往：「可以玩最久的」和「可以最快玩完的」。
可是要計算去每個縣市玩要花的確切時間太麻煩了，喵喵發現「縣市中要走最遠才能到的兩鄉鎮之間的距離P」（以下簡稱「鄉鎮最遠距離」，在Hints當中有一個例子）愈長，花費的時間就愈長，反之則反。因此，只要找到了「鄉鎮最遠距離」最長和最短的縣市，就找到了「可以玩最久的」和「可以最快玩完的」的縣市。
但是喵喵仍然覺得這樣要處理的東西太多。還好，他找到了一個具有法力的機器X，可以瞬間回答任兩個縣市哪一個的「鄉鎮最遠距離」比較長。
你的任務是幫喵喵操作機器X，並且告訴喵喵，可以玩最久的和可以最快玩完的縣市的「鄉鎮最遠距離」分別是多少，以方便他安排行程。
由於你的法力和計算能力都不強，你操作機器X的次數和取得縣市地圖的次數都沒辦法太多。保證任兩個縣市的「鄉鎮最遠距離」都不一樣。
Input Format
本題沒有輸入，如果你輸入了任何東西，可能會導致各種不可預期的結果。
請記得#include "lib1164.h"。以下是幾個你可以使用的函式：
int init();：你應該要在進行任何操作前呼叫這個函式。本函式會回傳喵喵候選的縣市數量N。
int query(int a, int b);：操作機器X的指令，代表詢問編號a和b的縣市哪一個「鄉鎮最遠距離」比較長。如果是a，回傳1，否則回傳0。如果呼叫次數超過限制，你會得到一個WA。
MAP getct(int a);：這個函數會回傳一個特殊的型別MAP代表編號a的縣市的地圖。假設變數名稱為p：p.m代表該縣市的鄉鎮數量；p.k代表該縣市的道路數量；p.x、p.y和p.len都是長度為k的陣列，代表這個縣市編號i的道路長度為p.len[i]，並連接編號p.x[i]和p.y[i]的鄉鎮。如果呼叫次數超過限制，你會得到一個WA。
（MAP型別的詳細資訊請參考Hints。）
void answer(int longest, int shortest);：計算完之後，呼叫這個函式提交答案，兩個參數依序為可以玩最久的和可以最快玩完的縣市的「鄉鎮最遠距離」。這個函式會幫你結束程式。
對於所有的測資，$2 \leq N,M,K \leq 10^ 6$。
保證答案一定在int範圍內。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~3) | $N,M,K \leq 4 \times 10^3$ | 20 |
| 2 (4~7) | $N,M,K \leq 4 \times 10^3$， 最多只能呼叫getct 5次 |
10 |
| 3 (8~11) | 最多只能呼叫getct 3次 | 11 |
| 4 (12~15) | 最多只能呼叫getct 2次、呼叫query 30N次 | 12 |
| 5 (16~19) | 最多只能呼叫getct 2次，且呼叫query的次數不超過最少足夠求解的次數 | 47 |
（註：對於第一組子任務來說，getct的次數無限制；而對於前三組子任務來說，query的次數無限制）
Output Format
本題沒有輸出，如果你輸出了任何東西，你將會獲得一個WA。
Sample Input 1
2
7 6 7
0 2 3
1 2 1
2 3 3
4 1 1
5 2 4
6 1 2
5 4 12
1 0 1
2 1 5
3 1 3
4 1 7
Sample Output 1
12 7
12 7
correct
Hints
typedef struct { int m, k; int *x, *y, *len; } MAP;
以上是MAP型別的原型。
這裡有一個測試用的標頭檔，可以用來測試。
該標頭檔接受以下輸入，數字間皆以空白分隔：
第一行：N；
接下來依序為編號0~N-1的縣市的資料，每個縣市的格式皆如下：
第一行：m, k, p；（分別是鄉鎮數量、道路數量和鄉鎮最遠距離）
接下來k行：x, y, len；（代表有一條長度為len的道路連接編號為x和y的鄉鎮）
此程式將會輸出三行：
第一行：你呼叫answer的兩個參數；
第二行：正確答案；
第三行：呼叫answer的參數是否與答案相同，相同輸出correct，否則輸出incorrect。
下圖為範例測資的圖示。
方框代表縣市，旁邊的數字是編號；圓圈代表鄉鎮，裡面的數字是編號；鄉鎮之間的線代表道路，旁邊的數字代表長度。
縣市0中走最遠才能到的兩鄉鎮是鄉鎮3和鄉鎮5，因此鄉鎮最遠距離等於4+3=7。
同理，縣市1的鄉鎮最遠距離等於12。
由於只有兩個縣市，鄉鎮最遠距離最長的是縣市1、最短的是縣市0。
Problem Source
Judge / Description by Yihda Yol
建國中學105學年度校隊選拔：複試pC
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~3 | 20 |
| 2 | 4~7 | 10 |
| 3 | 8~11 | 11 |
| 4 | 12~15 | 12 |
| 5 | 16~19 | 47 |