b257:
穿越蟲洞
Content
有 N 位運動員 (編為 1 至 N)，正在在一條長長的路上進行一項活動。這條路是由一些方格所組成，這些方格順序寫著一些連繼的自然數，即第一格上寫上1，第二格上寫上 2，如此類推。
以下稱這些格為路格。
這條路分成 N 段長度不一定相同的路段，每條路段均有一個起點路格及一個終點路格。
第一段號段的起點格為 1，其終點格為 D1，第二段路段的起點格為 D1+1，其終點格為 D2，第三段號段的起點格為 D2+1，其終點格為 D3，如此類推。
最初，這 N 個運動員按自己的編號順次各自站在自己的起點路格上，然後開始沿著大數字的方向走。
這條路上有 M 個蟲洞，每個蟲洞連接著兩個不同的路格。
當運動員踏進一個蟲洞的一端的路格上時，就會被傳送到蟲洞連接的另一端路格上，而當一個運動員被送到另一端的路格時，他會繼續向大數方向前進，直至他到達其中一個終點為止。
這些蟲洞有以下的特點:
- 蟲洞的兩端分別出現在兩個不同的路段上
- 蟲洞的兩端不會出現在任何起點或終點上
- 任何一個路格最多只會是一個蟲洞的端口
- 蟲洞的端口不會出現在這 N 條路段以外的任何路格上
- 任何蟲洞的組合，均不會構成任何環的出現。換言之，每一位運動員最終必定可以到達其中一個終點
現在我們想知道的是每一個運動員最終會到達哪一個終點。
Input
輸入包括若干組測試數據。每組數據包括有以下格式的一組資料:
- 每組資料的第一行爲兩個正整數 N 和 M，N 表運動員的數目，M 則代表蟲洞的數目 (2 ≤ N ≤ 500，1 ≤ M ≤ 4,000)
- 第二行上有 N 個正整數每一個正整數，這 N 個數順次代表著 N 個終點所在的路格編號。這些編號均小於 109)
- 隨後有 M 行，每行有一對正整數，代表一個蟲洞的兩個端口所在的路格的編號
輸入的最後一行，有兩個 0，代表輸入的結束。
Output
對應於每一組測試數據，請輸出一行，其上含有 N 個正整數，它們順次代表運動員 1 至 N 所到逹的絡點的路格的編號。
Sample Input
#1
3 3 6 10 15 3 9 8 12 14 5 0 0
Sample Output
#1
10 6 15
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (1%): 1.0s , <1K
不公開 測資點#1 (9%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <1M
不公開 測資點#8 (10%): 1.0s , <1M
不公開 測資點#9 (10%): 1.0s , <10M
不公開 測資點#10 (10%): 1.0s , <10M
不公開 測資點#0 (1%): 1.0s , <1K
不公開 測資點#1 (9%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <1M
不公開 測資點#8 (10%): 1.0s , <1M
不公開 測資點#9 (10%): 1.0s , <10M
不公開 測資點#10 (10%): 1.0s , <10M
Hint ：
對於以上的例子，各運動員所走的路線如下:
- 第一位運動員: 1>>3=>9>>10
- 第二位運動員: 7>>8=>12>>14=>5>>6
- 第三位運動員: 11>>12=>8>>9=>3>>5=>14>>15
其中 "=>" 表示穿越了蟲洞，">>" 表示在正常路上跑。
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||