回分類題庫
h056: H.幼稚國王的行程
關鍵字: NPSC 2008 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 12 Times / 6 Users | Submit : 27 Times / 11 Users | Accepted rate : 55%
題目加入時間 : 2011-11-10 10:48

Content: 简体中文

幼稚國王實在是再也受不了幼稚國裡面發生的幼稚事情了,於是他決定要出去旅行。

在幼稚王國內,有許許多多個城市,在城市之間有著一些相連幹道將這些都市們連接起來。但是由於幼稚總理到現在都還沒有被選出來,整個王國內簡直是一團混亂,這些道路們現在暫時只能單向連通。

幼稚國王每天的行程一早都會先到某個城市的旅館訂房與放好行李,休息到中午才會從旅館出發,並且希望能到盡量多的城市去玩。但是每天晚上十一點以前一定都要回到早上一開始的下榻的飯店休息。到了隔天一大早,幼稚國王再出發到另外的城市新的旅館,繼續他的旅程。

幼稚國王除了每天飯店下榻的城市以外,他不希望在一天內重複造訪同一個都市超過三次,因為他認為如果真的有什麼需要再回來玩的話,為什麼不第一次來的時候就仔細參觀呢? 這樣子跟那些幼稚鬼又有什麼分別呢..

當然,在這趟旅途的目的裡,幼稚國王想要盡可能的多參觀一些景點,對於他而言,一整天如果都花再同一個城市裡面,那是相當乏味的,幼稚國王完全不願意整整一整天的行程竟然就在同一個城市裡面度過了,真的是太可怕了。

不幸的是,幼稚國王那能幹的幼稚大臣現在正在忙著處理幼稚總理的選別,沒有辦法分心來處理幼稚國王的行程。身為幼稚國榮耀的一員,能不能請你幫忙幼稚國王挑選出哪些適合每天早上下榻的城市呢? 

Input:

第一行有一個數字 k , 1 <= k <= 100 代表共有 k 筆測資

每筆測資第一行,有三個整數 N, M, D
 1 <= N<= 1000 代表共有 N 個城市,編號從 1 ~ N
 1 <= M <= N^2 代表共有 M 條幹道
 1 <= D <= 10000 代表幼稚國王每天最多可以旅行多遠的路程
 此路程不含早上前往新旅館的距離 

接下來 M 行,每行有三個整數 u, v , d
 1 <= u, v <= N
 0 <= d <= 10000 代表有一條距離為 d 的幹道是從 u 連接到 v 的 

Output:

每筆測資輸出兩行,
第一行有一個整數 P,代表總共有 P 個適合幼稚國王早上下榻的城市
第二行有 P 個整數,分別是這 P 個都市的編號,按照順序由小到大排列,數字間以空白間隔

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
2 1 4
2 1 10
4 5 9
4 3 10
2 1 6
3 1 2
1 3 3
3 4 1

Sample Output :

0
2
1 3

Hint :

Author :

NPSC 2008 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum