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; 
}