Problem : 65 - A. 一兔二窟

Problem Statistics

Solved Member: 17　　Submission: 112　　User Tried: 24

Statement:

HH挖了n個洞穴，每個洞穴間可能會有道路連通，這些道路總共有m條。

俗話說狡兔三窟，但HH卻只有兩窟，哭哭。(因為不是每個洞穴都能當巢穴...)

但HH不灰心，為了彌補只有兩窟的遺憾，HH規劃了一連串的道路設計，準備開挖，現在HH要請你幫忙決定那些道路該開挖，為了方便討論，HH的巢穴編號為1與n。

對於第i條規劃的道路，若可以縮短兩巢穴的最短距離，則HH會馬上去開挖，若無法，則會將那張設計圖丟棄。接著再去決定下個道路設計是否要興建。(由於HH是馬上去開挖，故之後的道路也要考慮喔！)

Input:Output:

第一行有3個正整數n,m,q，表示原本有n個洞穴，m條通道，與q張道路設計圖。

接下來的m行是道路資訊，每行三個整數u,v,w，表示洞穴u與洞穴v之間有一條長度為w的雙向通到。

接下來有q行，每行表示一條通道的設計圖。

其中1 <= n <= 100，1 <= m <= n*(n-1)/2，1 <= q <= 10000，1 <= u,v <= n，1 <= w <= 1000000。

依序考慮每張設計圖，若可以縮短兩巢穴的距離輸出1，並馬上去開挖，若無法則輸出0。

Sample Input:Sample Output:

4 5 5
1 4 7
1 2 2
2 4 7
3 4 2
1 3 6
1 3 5
1 4 6
2 4 4
1 3 3
2 4 2

0
1
0
1
1

Source:

OIG 1 Stage 3

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	32767kb
1-ocen	1000ms	32767kb
1	1000ms	32767kb	10
2-ocen	1000ms	32767kb
2-1	1000ms	32767kb	10
2-2	1000ms	32767kb
3-ocen	1000ms	32767kb
3-1	1000ms	32767kb	10
3-2	1000ms	32767kb
4-ocen	5000ms	32767kb
4-1	1000ms	32767kb	10
4-2	1000ms	32767kb
5-1	1000ms	32767kb	10
5-2	1000ms	32767kb
6-1	1000ms	32767kb	10
6-2	1000ms	32767kb
7-1	1000ms	32767kb	10
7-2	1000ms	32767kb
8-1	1500ms	32767kb	10
8-2	1000ms	32767kb
9-1	1500ms	32767kb	10
9-2	1000ms	32767kb
10-1	2000ms	32767kb	10
10-2	1000ms	32767kb