2012-12-01 12:19:41Morris
[ZJ] a586. 4. 捷運計價問題
內容 ：
「天龍國」為了促進觀光，推出捷運觀光地圖。只要持有觀光護照者搭乘捷運將會有特別的優待，並依照下列三種計費規定收費：
- 基本票價十元。
- 每經過三站票價加五元。
- 轉乘不同捷運路線加五元。
以
下圖為例，若起點為 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元)。
現在請你(妳)設計一個程式，當遊客決定好捷運的起點及終點時，能為每一個來此觀
光的遊客計算票價(若有多條路線可從起點抵達終點時，請計算出最便宜的票價)。
輸入說明
：
第一行有一個正整數 N(1≤N≤500)，N代表接下來有 N筆目前捷運站的資訊。
自第二行到第 N+1行，每一行代表捷運任意兩站連通的資訊，每一站命名為一個大寫英文字母後接數字，其中開頭的大寫英文字母代表所在路線，數字 m為小於等於 100的正整數 (1≤m≤100)。此兩站中間以一個空格區分，兩站之間雙向都可以連通。
第 N+2行代表所要規劃路徑的起點與終點，中間以一個空格區分。
輸出說明
：
請輸出一個數值，代表規劃的起點到終點之最便宜票價。
範例輸入
：
輸入範例一： 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 輸入範例二 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
範例輸出 ：
輸出範例一 20 輸出範例二 20
提示
：
出處
：
101年北三區資訊學科能力競賽
(管理：pcshic)
寫不短的單源最短路。
#include <stdio.h>
#include <vector>
#define ch(i) (i-'A')
using namespace std;
vector<int> g[2600];
int main() {
int n, x, y, dis[2600][2], used[2600], i, j;
char xx[10], yy[10];
scanf("%d", &n);
while(n--) {
scanf("%s %s", xx, yy);
sscanf(xx+1, "%d", &x);
sscanf(yy+1, "%d", &y);
x = ch(xx[0])*100 + x-1;
y = ch(yy[0])*100 + y-1;
g[x].push_back(y);
g[y].push_back(x);
}
scanf("%s %s", xx, yy);
sscanf(xx+1, "%d", &x);
sscanf(yy+1, "%d", &y);
x = ch(xx[0])*100 + x-1;
y = ch(yy[0])*100 + y-1;
for(i = 0; i < 2600; i++)
dis[i][0] = dis[i][1] = 0xfffff, used[i] = 0;
dis[x][0] = dis[x][1] = 0;
for(i = 0; i < 2600; i++) {
int mn = 0xffff, tn = -1;
for(j = 0; j < 2600; j++) {
if(used[j] == 0 && dis[j][0]/3*5+dis[j][1] < mn)
mn = dis[j][0]/3*5+dis[j][1], tn = j;
}
if(tn < 0) break;
used[tn] = 1;
for(j = 0; j < g[tn].size(); j++) {
if((g[tn][j]/100 != tn/100)*5+(dis[tn][0]+1)/3*5+dis[tn][1] < dis[g[tn][j]][0]/3*5+dis[g[tn][j]][1]) {
dis[g[tn][j]][0] = dis[tn][0]+1;
dis[g[tn][j]][1] = dis[tn][1]+(g[tn][j]/100 != tn/100)*5;
}
}
}
printf("%d\n", dis[y][0]/3*5+dis[y][1]+10);
return 0;
}