a586.
4. 捷運計價問題
Content
「天龍國」為了促進觀光，推出捷運觀光地圖。只要持有觀光護照者搭乘捷運將會有特別的優待，並依照下列三種計費規定收費：
- 基本票價十元。
- 每經過三站票價加五元。
- 轉乘不同捷運路線加五元。
以下圖為例，若起點為 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
公開 測資點#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:
| ID | User | Problem | Subject | Hit | Post Date |
| 39956 |
|
a586 | 154 | 2024-04-15 09:21 |