2013年8月13日 星期二

1198 - The Geodetic Set Problem

G = (V, E) 表示一連通圖,不存在 loops(自己連自己) 和重覆的邊,V, E 分別表示節點與邊。

對於 u, v V 必然會存在一條最短路徑,而 I (u, v) 定義為在 u - v 最短路徑上的點所產生的集合,而 S V


如果 I(D) = V,則這節點集合 D 被稱作為 G 的其中一個 geodetic set The geodetic set problem 就是要檢驗 D 是否為 geodetic set

以上圖為例,I(2, 5) = {2, 3, 4, 5},即所有可能在最短路徑上的所有點,然而
I(2, 5) 並不是一個 geodetic set,因為並不等於 {1, 2, 3, 4, 5}。

假如 D = {1, 2, 5},則 I(D) = V,同時 {1, 3, 4} {1, 4, 5} 也都是 geodetic set,但
{3, 4, 5} 卻不是,因為節點 1 並不在 I(D) 中。


Input

輸入有多組測資,每組第一行有一個整數 n (2 <= n <= 40) 表示圖有多少節點。


接下來會有 n 行,在第 i(1 <= i <= n)上會有數個整數,表示與節點編號 i 相連的點。

接著會有一行一個整數 q,表示接下有多少組詢問
 

每組詢問一行,行上的每個整數 D 集合內的節點編號。
Output

對於每組詢問的 D,判斷 D 是否為
geodetic set

Sample Input

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

 
Sample Output

yes
yes
no
yes
yes
no

925 - No more prerequisites, please!

最近,我正在準備給予少部分學生的畢業課程指導,向同事要課程之間的關係,而有部分課程需要先修課程,定義這先修課程的集合為 c,也就是說學生必須先修過 c 的所有課程,才能修這門課。

不過同事太熱心了,給了過多的資訊,過多是什麼意思,接下來我會解釋 ...:

  • 假設有課程名為 ca, cb, cc, cd, cd
  • 必須先修過 ca 才能修 cb必須先修過 cb 和 cc 才能修 cd
    必須先修過 cd 才能修 ce。
  • John 負責課程 cd,告訴我先修課程為 cc, cb, ca
  • Elizabeth 負責課程 ce,告訴我先修課程為 cd, cc, cb, ca
但我發現只需要說明先修課程 cc, cb,就可以修 cd 課程,因為 ca 已經在 cb 的先修課程中。同樣地,只需要說明 cdce 的先修課程即可,因為 cd 已經有 cc, cb, ca 的先修課程條件了。

不幸地,並不是每個同事都給予最小化的先修課程,太多太多的資訊蜂擁而來,希望有個機器人可以幫忙處理這些資訊,並寫告訴我最小化的先修課程。


Input

輸入第一行有一個整數,表示接下來會有多少測資組,至多 1000 組。

每組第一行會有一個整數 k,表示課程總數,而接下來會有 k 行,分別為課程名稱。
課程名稱由小寫英文字母構成,長度最多為 20。


接下來有一個整數 j,表示接下來有 j 行先修課程的資訊。
每一行第一個為課程名稱,第二個整數為先修課程的個數,接下來為先修課程的名稱。

(0 < k, j <= 120)

Output

按照輸入順序,依序輸出該課程的先修課程清單,對於先修課程清單同樣按照輸入順序輸出。

Sample Input

2
5
cc
ca
ce
cb
cd
3
ce 4 cd cb cc ca
cd 3 cb cc ca
cb 1 ca
9
dg
di
dc
df
de
dd
da
dh
db
7
dg 3 da de df
dd 2 da db
df 1 de
dc 1 db
dh 5 da de dg df dc
de 2 da dd
di 2 df dd


Sample Output 

cb 1 ca
cd 2 cb cc
ce 1 cd
dc 1 db
dd 2 da db
de 1 dd
df 1 de
dg 1 df
dh 2 dc dg
di 1 df
 

274 - Cat and Mouse

房子中有一隻貓和一隻老鼠,貓和老鼠各自選一間房間為貓窩和鼠窩,牠們會從窩起身到房子的其他房間逛逛,而貓只能通過貓門到另一個房間,而這種貓門都是單向通行的,同樣地,老鼠也有鼠門,牠們只會使用自己的門,不會使用對方的門進出。


給房子地圖資訊,寫程式判斷下面 2 點資訊:
  1. 是否存在牠們會碰到面的房間。
  2. 老鼠有沒有可能從鼠窩出門(一定要出去到至少一個房間)並且回到鼠窩,途中不會有任何房間有貓的存在疑慮。
例如:從圖中可發現,貓和老鼠可能會在房間 1, 2, 3 碰面,而由於貓不可能出現在房間 4,因此老鼠可以從鼠窩到房間 4 後返回鼠窩。


Input

輸入第一行有一個整數,表示測資組數。測資組間會有一行空行。

對於每組測資第一行會有三個整數 n, cat, mouse,表示房間個數、貓窩、鼠窩編號。
接下來會有數行描述貓門的單向資訊,每行有兩個整數 A, B,表示 A 到 B 存在貓門單向通行,當 A = B = -1,則接下來換鼠門的單向資訊,同樣每行有兩個整數 A, B,表示 A 到 B 存在鼠門單向通行。
 

Ouput

對於每組測資輸出一行,判斷的 2 點資訊,以 'Y' 或 'N' 表示。

測資組間空一行。

Sample Input

1

5 3 5
1 2
2 1
3 1
4 3
5 2
-1 -1
1 3
2 5
3 4
4 1
4 2
4 5
5 4
Sample Output
Y Y

186 - Trip Routing

加州汽車俱樂部(CCC)打算提供會員旅行路線服務,寫一個程式讀取道路資訊以及詢問的兩地,計算出兩地的最短距離。

對於每組詢問, 輸出經過的城市名稱、道路名稱、距離。

Input
 
輸入分成兩個部分,

第一部分描述高速公路的地圖資訊,每一行描述一條高速公路的一小段,用逗號分隔成 4 個欄位,第一欄位表示起點城市名稱,第二欄位表示終點城市名稱,第三欄位表示公路名稱,第四欄位用一個正整數描述公路的長度。

(城市名稱長度最多 20,公路名稱長度最多 10)

第一部分直到空行出現,宣告結束。


第二部分描述詢問的兩地資訊,每一行詢問一組兩地距離,用逗號隔開起點城市與終點城市。

最後用 EOF 最為程式結束。

Output

輸出格式請參考範例輸出,每組詢問前印出 2 個空行


Sample Input

San Luis Obispo,Bakersfield,CA-58,117
Bakersfield,Mojave,CA-58,65
Mojave,Barstow,CA-58,70
Barstow,Baker,I-15,62
Baker,Las Vegas,I-15,92
San Luis Obispo,Santa Barbara,US-101,106
San Luis Obispo,Santa Barbara,CA-1,113
Santa Barbara,Los Angeles,US-101,95
Bakersfield,Wheeler Ridge,CA-99,24
Wheeler Ridge,Los Angeles,I-5,88
Mojave,Los Angeles,CA-14,94
Los Angeles,San Bernardino,I-10,65
San Bernardino,Barstow,I-15,73
Los Angeles,San Diego,I-5,121
San Bernardino,San Diego,I-15,103

Santa Barbara,Las Vegas
San Diego,Los Angeles
San Luis Obispo,Los Angeles
 
Sample Output

From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
Santa Barbara        Los Angeles          US-101        95
Los Angeles          San Bernardino       I-10          65
San Bernardino       Barstow              I-15          73
Barstow              Baker                I-15          62
Baker                Las Vegas            I-15          92
                                                     -----
                                          Total        387


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
San Diego            Los Angeles          I-5          121
                                                     -----
                                          Total        121


From                 To                   Route      Miles
-------------------- -------------------- ---------- -----
San Luis Obispo      Santa Barbara        US-101       106
Santa Barbara        Los Angeles          US-101        95 
                                                     -----
                                          Total        201

1233 - USHER

在紐西蘭的一個大教堂中,每當禮拜結束後,牧師將會給一個收集盒,而這個盒子最多裝 c 元,當教友收到這個盒子時,他將會放入一些錢並且交給下一個教友。現在裡頭混有一個不明人士,每當盒子傳到他手上時,他將會抽出 1 元放入口袋,然後將盒子交給其中一名教友。

每名教友的行為,分別有會傳給哪些教友,以及每次盒子經過時他會放多少錢進去。如果在放的過程中盒子滿了,則將會把盒子立刻地傳到牧師那邊。


計算這個不明人士在最好的情況下,他能偷拿多少錢。

Input

輸入第一行有一個整數,表示接下來會有多少測資組。



每組測資第一行有兩個整數 b, p ,分別表示盒子容量、教友的個數。

(1 <= b <= 1,000,000, 1 <= p <= 500),教友編號為 1, 2, 3, ..., p,不明人士編號為 0。
接著會有一個整數 q,表示這個不明人士可以傳給其中多少教友,則接下來會有 q 個整數緊接在後,表示不明人士可以傳的教友編號。





接下來會有 p 行,在其中第 i 行表示教友 i 的行為,每行第一個整數表示他會有多少行為,每組行為第一個整數為他放入的金額,第二個整數則表示他放完這筆金額後會傳給的人。


Output


對於每組測資,輸出不明人士最多能拿多少錢




測資說明:
盒子最多能放 10 元,而有 2 位教友,其中不明人士會傳給 1 或 2。而教友 1 會放入 6 元後傳給不明人士,或者是放入 4 元後傳給教友 2。教友 2 則是會放入 5 元後傳給不明人士。



不明人士打算只傳給教友 2,教友 2 放入 5 元後,被不明人士抽走 1 元,盒子內部只剩 4 元,再進行一次,到不明人士手中時,又抽走 1 元剩下 7 元,最後傳給教友 2 時,放入 5 元已經超過盒子容量便直接傳給牧師收走。
 
Sample Input



1 
10 2 
2 1 2 
2 6 0 4 2 
1 5 0 
0

Sample Output


2

12319 - Edgetown's Traffic Jams

Edgetown 以互相通信為驕傲的城市,也就是說可以從城市的任何一地到達其他所有地方。對於城市的每一條路連接兩個路口,也就是說每條路中間不會有奇他的路口,同時也不會有兩條路兩端連接相同的路口。城市當局每年都必須確保道路的連通性,也就是不會有被孤立的路口,而有些道路是雙向的。



下圖表示有 11 個路口(以 '*' 表示) 和 10 條道路。




最近有幾個地方產生交通壅塞,專家建議將雙向道改成單向道,然而這項工程要特別小心,否則將會有些地方被孤立無法到達,又或者使兩地的最短路徑增大。


經過數次討論,市長的顧問打算同意兩地之間的最短距離增大 A 倍加一個常數 B,也就是說當兩地最短距離 x,更改過後的距離最多為 Ax+B。





寫一個程式,判斷新的建議是否符合市長顧問的要求。


Input

輸入有多組測資,每組測資有兩張圖的描述。
 
每組第一行有一個整數 n (3 <= n <= 100),表示路口的個數,路口編號為 1, 2, 3, ..., n

接下來會有 n 行,在第 i 行(1 <= i <= n) 上會有數個整數,表示路口 i 相連到其他路口的資訊。

接下來會有 n 行,在第 i 行(1 <= i <= n) 上會有數個整數,表示在新的規劃中,路口 i 相連到其他路口的資訊。

最後一行會有兩個整數 A, B (0 <= A, B <= 10)

Output

對於每組測資,輸出 "Yes" 或 "No" 表示是否接受新的建議。

Sample Input

5
1 2 3
2 1 5
3 4 5 1
4 3 5
5 2 3 4
1 2
2 5
3 1 4
4 5
5 3
1 2
5
1 2 3
2 1 5
3 4 5 1
4 3 5
5 2 3 4
1 2
2 5
3 1 4
4 5
5 3
2 0
3
1 2
2 1 3
3 1 2
1 2
2 3
3 1
0 2
0

Sample Output

Yes
No
Yes

1247 - Interstar Transport

到了西元 2100 年,對於銀河系上的太空旅行已經實現了,星際旅行社打算規劃星球旅行,將兩個最受歡迎的星球設計路線,這路線的花費使用 Galaro 為貨幣單位,並且也出了許多不同語言版本,然而並不是任兩個星球都有被規劃路線,兩個星球間的旅行被限制於太空旅行清單中。

幫助旅客規劃他們的行程,星際旅行社想要提供一款行動 App 找到最佳旅行選擇,最加取決於兩個星球間的旅程花費, 給定起點與終點星球,找到一條路徑有最少花費,並且輸出路程中的每一個星球,如果有同一條路具有相同花費時,則找中間經過最少個星球為最佳路徑。每組測資只會存在一組最佳路徑。

條件限制

  1. 星球個數 s (1 <= s <= 26),且每個星球使用大寫英文字母表示 'A', 'B', 'C', ..., 'Z'。
  2. 星球間,最多存在 200 條可進行太空旅行的直通道路。
  3. 每條路線的花費都是一個正整數小於等於 100。
Input

輸入第一行會有兩個整數 s, p
接下來會有 p 行,每行上有兩個字元 ei , ej 以及一個整數 dij
表示 ei , e間可以進行太空旅行,且花費為 dij
緊接著會有一個整數 n (1 <= n <= 20),表示有多少組詢問,
接下來會有 n 行,每行上有兩個字元 ek , em,表示要求這兩個星球的最少花費路徑。

Output

對於每組詢問輸出一行,每個星球編號間以空白隔開,順序為從起點到終點從左至右輸出。

Sample Input

5 7 
A B 1
B C 2
C D 3
D E 2
E A 1
A D 3
A C 4
3 
B D 
A D 
E C
Sample Output
B A D 
A D 
E A B C