a586: 4. 捷運計價問題
Tags :
Accepted rate : 64人/71人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-10-14 07:57

Content
「天龍國」為了促進觀光,推出捷運觀光地圖。只要持有觀光護照者搭乘捷運將會有特別的優待,並依照下列三種計費規定收費: 
  1. 基本票價十元。 
  2. 每經過三站票價加五元。 
  3. 轉乘不同捷運路線加五元。
以下圖為例,若起點為 B1,終點為 G2,若搭乘路線為: B1-B2-B3-B4-G1-G2,所需票價為 20元(=10+5*1+5,為基本票價 10元+經過 5站需 5元+轉乘 5元);若搭乘路線為: B1-B2-R1-R2-R3-G2,所需票價為 25元(=10+5*1+5*2,為基本票價 10元+經過5站需 5元 +轉乘兩種路線 10元)。
現在請你(妳)設計一個程式,當遊客決定好捷運的起點及終點時,能為每一個來此觀
光的遊客計算票價(若有多條路線可從起點抵達終點時,請計算出最便宜的票價)。 
Input
第一行有一個正整數 N(1≤N≤500),N代表接下來有 N筆目前捷運站的資訊。
 
自第二行到第 N+1行,每一行代表捷運任意兩站連通的資訊,每一站命名為一個大寫英文字母後接數字,其中開頭的大寫英文字母代表所在路線,數字 m為小於等於 100的正整數 (1≤m≤100)。此兩站中間以一個空格區分,兩站之間雙向都可以連通。
 
第 N+2行代表所要規劃路徑的起點與終點,中間以一個空格區分。
Output

請輸出一個數值,代表規劃的起點到終點之最便宜票價。

Sample Input #1
11
B1 B2
B2 B3
B3 B4
B4 B5
B4 G1
G1 G2
G2 G3
R1 R2
R2 R3
B2 R1
R3 G2
B1 G2
Sample Output #1
20
Sample Input #2
12
R1 R2
R2 R3
R3 R4
R4 R5
R5 R6
R6 R7
R7 B1
R7 Y1
Y1 B1
Y1 R1
Y1 G1
G1 R1
G1 B1
Sample Output #2
20
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
Hint :
Tags:
出處:
101學年度北基區資訊學科能力競賽 [管理者:
pcshic (PCSHIC)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」