经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。

 

输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。

 

如果徐总能到达目的地，输出最短的时间；否则，输出“-1”。

 

 

Sample Output

 

Author

lgx

 

#include<bits/stdc++.h>

#define N 170

#define mes(x) memset(x, 0, sizeof(x));

const long long mod = 1e9+;

const int INF = <<;

using namespace std;

map<int ,int >mp;

int plat[N][N];

int dis[N],dir[N];

int dj(int start,int end, int n){

    int i, min, t, j;

    //if(start == end) return 0;

    if(!(start&&end)) return -;

    for(i=;i<=n;i++) dis[i] = plat[start][i];

    for(j=;j<=n;j++){

        min = INF;t=;

        for(i=;i<=n;i++){

            if(min > dis[i] && !dir[i] ){

                min = dis[i];

                t = i;

            }

        }

        dir[t] = ;

        for(i=;i<=n;i++){

            if(dis[i] > dis[t] + plat[t][i])

                dis[i] = dis[t] + plat[t][i];

        }

        }

        if(dis[end] < INF) return dis[end];

        return -;

}

int Hash(char* s){

    long long seed=;// 31 131 1313 13131 131313 etc..

    long long hash=;

    while(*s=='')s++;//处理

    while(*s)

        hash=hash*seed+(*s++);

    return (hash & 0x7FFFFFFF);

}

int main()

{

    char s1[],s2[];

    int n, start, end, t, l, ans, ha1, ha2, i, j;

    while(~scanf("%d", &n)&&n!=-){

        for(i=;i<=;i++)

            for(j=;j<=;j++)

            {

                if(i==j) plat[i][j] = ;

                else

                plat[i][j] = INF;

            }

        memset(dir, , sizeof(dir));

        mp.clear();

        scanf("%s%s", s1, s2);

        start = Hash(s1); end = Hash(s2);

        t = ;

        while(n--){

            scanf("%s%s%d", s1, s2, &l);

            ha1 = Hash(s1);ha2 = Hash(s2);

            if(!mp[ha1]) mp[ha1] = t++;

            if(!mp[ha2]) mp[ha2] = t++;

            if(plat[mp[ha1]][mp[ha2]] > l){

            plat[mp[ha1]][mp[ha2]] = l;

            plat[mp[ha2]][mp[ha1]]= l;

            }//有毒啊，双向的

        }

        ans = dj(mp[start], mp[end], t-);

        printf("%d\n", ans);

    }

    return ;

 }