hoj 經典最短路 回家

[cpp]
/*這道題很不錯，推薦下。貌似也是工大原創的題吧。題意大概就是給一個圖。城市和城市之間有邊權，從一個城市到一個城市需要轉車，也有點權，
而這個值需要取決於該節點的前一條邊和後一條邊的交通方式。求這樣一種情況下的最短路。
這樣的請看下需要增加一維來記錄交通方式的選擇。其余的和dij是一樣的。
還有可以用map來記錄重復的字符串。*/ 
#include <iostream> 
#include <stdio.h> 
#include <cstring> 
#include <map> 
using namespace std; 
const int maxn=101; 
int g[maxn][maxn][2]; 
int dist[maxn][2]; 
bool vis[maxn][2]; 
int main() 
{ 
    map<string,int> mp; 
    int n,m,d,to=1,k; 
    char s[21],s1[21],s2[21],way[7]; 
    while(scanf("%s",s)==1) 
    { 
        mp.clear(); 
        mp[s]=1; 
        n=1; 
        scanf("%d",&m); 
        memset(g,0x7f,sizeof(g)); 
        memset(dist,0x7f,sizeof(dist)); 
        while(m--) 
        { 
            scanf("%s %s %s %d",way,s1,s2,&d); 
            if(way[0]=='t') k=1; 
            else k=0; 
            if(mp[s1]==0) mp[s1]=++n; 
            if(mp[s2]==0) mp[s2]=++n; 
            int a=mp[s1],b=mp[s2]; 
            if(strcmp(s1,"Harbin")==0) to=a; 
            if(strcmp(s2,"Harbin")==0) to=b; 
            g[a][b][k]=g[b][a][k]=d; 
        } 
        memset(vis,false,sizeof(vis)); 
        for(int i=2; i<=n; i++) 
            for(int k=0; k<2; k++) 
                dist[i][k]=g[1][i][k]; 
        dist[1][0]=dist[1][1]=0; 
        vis[1][0]=vis[1][1]=true; 
        for(int i=0;i<2*n;i++) 
        { 
            int mi=1000000000; 
            int K,T; 
            for(int j=1;j<=n;j++) 
            for(int k=0;k<2;k++) 
            { 
                if(!vis[j][k]&&dist[j][k]<mi) 
                { 
                    mi=dist[j][k]; 
                    K=k; 
                    T=j; 
                } 
            } 
            vis[T][K]=true; 
            for(int j=1;j<=n;j++) 
            for(int k=0;k<2;k++) 
            { 
                dist[j][k]=min(dist[j][k],dist[T][K]+g[T][j][k]+(K==k?3:10)); 
            } 
        } 
        printf("%d\n",min(dist[to][0],dist[to][1])); 
    } 
    return 0; 
}