回分類題庫
d019: 2007 程式達人 B - 旅行者來自何方
出處:

Difficulity : 2
Accepted : 12 Times | Submit :20 Times | Clicks : 1640
Accepted : 10 Users | Submit : 11 Users | Accepted rate : 91%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2008-10-10 08:52

Content :

給定一個包含連接路徑和行走機率的任意地圖,已知旅行者所抵達的終點,計算旅行者所有可能的出發點及其機率分佈。地圖中,所有路線都是單行道,如果我們可以從甲地點走到乙地點的話,就不能從乙地點走到甲地點。

地圖的表示法:
本問題中的「地點」分成三類:中間點、終結點和出發點。地圖中的地點以有方向的路徑連接,我們稱每一路段的終點為該路段起點的「可達地點」。

 

例如:假定我們有上圖所示的地圖。
(A (D 0.4) (E 0.6))
(B (D 0.1) (E 0.7) (F 0.2))
(C (E 0.7) (F 0.3))
(D (G 0.2) (H 0.8))
(E (G 0.5) (H 0.5))
(F (G 0.8) (H 0.2))
(G)
(H)
(A 0.3)
(B 0.4)
(C 0.3)

給定這一個地圖和行走機率的分佈,如果旅行者抵達地點H,則此人原本是從 A、B 或者 C 出發的機率分別是0.3742、 0.3783 和 0.2475。

Input :

第一列是旅行者所抵達的終點站的地點名稱,隨後則是地圖資料。所有地點皆為英文的大寫字母。機率則為大於 0 且小於或等於 1 的數字,此數字精確到小數點後一位。

Output :

根據出發點的英文字母,由小而大依序列出所有可能的出發點及其機率。不同的出發點之間以一空白隔開。每個可能的出發點及機率以(出發點 機率)的形式呈現;出發點與機率之間以一空白隔開,機率必須精確到小數點後四位。

Sample Input :

H
(A (D 0.4) (E 0.6))
(B (D 0.1) (E 0.7) (F 0.2))
(C (E 0.7) (F 0.3))
(D (G 0.2) (H 0.8))
(E (G 0.5) (H 0.5))
(F (G 0.8) (H 0.2))
(G)
(H)
(A 0.3)
(B 0.4)
(C 0.3)

Sample Output :

(A 0.3742) (B 0.3783) (C 0.2475)

Hint :

解題率:0/21

Author :

(管理員:MrWrongAnswer)

  Solve it!   Status Forum (0)

C++
C
JAVA
36759. nothinglo (4 ms , 549KB)
51264. uglyman (6 ms , 546KB)
36757. MK (6 ms , 560KB)
42306. cp99303052 (8 ms , 473KB)
36758. MK (9 ms , 549KB)
55126. ag100 (1 ms , 268KB)
55127. ag100 (5 ms , 273KB)
86928. nccucs105703018 (6 ms , 273KB)
50744. king_of_laba (6 ms , 294KB)
44176. QQ (6 ms , 290KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡