2013年7月11日 星期四

1112 - Mice and Maze

實驗室中的老鼠被訓練要逃離迷宮,迷宮由許多個小房間相連構成。然而有許多障礙物在房間的通道中,如果要經過會有時間上的罰分。老鼠只會有一種方式去抵達另一個房間,不會有其他的方式。

假設所有老鼠現在正在被訓練, 放置於任何一個迷宮中的房間,規劃一條路使得牠們能在最短時間內抵達終點的房間。

即將做以下的實驗:將老鼠放置每一個房間,並且按下倒數計時器,當時間停止時,計算所有逃離迷宮的老鼠個數。

寫一個程式去計算老鼠個數,根據給定的迷宮以及時間限制。假設每個點都可以抵達終點,而所有房間都可以有任意數量的老鼠,

Input 

輸入第一行會有一個整數,表示接下來會有幾組測資,測資組間會有一行空白行。

每組第一行會有一個整數 N ( N ≤ 100 ),表示小房間的個數,編號為 1, 2, ..., N
第二行會有一個整數 E,表示終點房間的編號,
第三行會有一個整數 T,表示時間倒數的秒數。
第四行會有一個整數M表示連接兩房間的個數。
接下來會有 M 行,每行上會有三個整數 a, b, time,表示 ab 需要花費 time 的時間,單向的道路。

Output 

對於每組測資,輸出逃離迷宮的老鼠個數,測資組間空一行。

Sample Input 

1

4 
2 
1
8
1 2 1
1 3 1
2 1 1
2 4 1
3 1 1
3 4 1
4 2 1
4 3 1

Sample Output 

3