2012-12-01 12:19:41Morris

[ZJ] a586. 4. 捷運計價問題

內容 :

「天龍國」為了促進觀光,推出捷運觀光地圖。只要持有觀光護照者搭乘捷運將會有特別的優待,並依照下列三種計費規定收費: 
  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元)。
現在請你(妳)設計一個程式,當遊客決定好捷運的起點及終點時,能為每一個來此觀
光的遊客計算票價(若有多條路線可從起點抵達終點時,請計算出最便宜的票價)。 

輸入說明 :

第一行有一個正整數 N(1≤N≤500),N代表接下來有 N筆目前捷運站的資訊。

自第二行到第 N+1行,每一行代表捷運任意兩站連通的資訊,每一站命名為一個大寫英文字母後接數字,其中開頭的大寫英文字母代表所在路線,數字 m為小於等於 100的正整數 (1≤m≤100)。此兩站中間以一個空格區分,兩站之間雙向都可以連通。

第 N+2行代表所要規劃路徑的起點與終點,中間以一個空格區分。

輸出說明 :

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

範例輸入 :help

輸入範例一:
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;
}