Problem Description

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

 

Input

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

 

Output

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

 

Sample Input

 

Sample Output

 

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define INF 0x3f3f3f3f

#define MM(x) memset(x,0,sizeof(x))

#define MMINF(x) memset(x,INF,sizeof(x))

using namespace std;

typedef long long LL;

const int N=20100;

struct info

{

	int to;

	int dx;

	int pre;

}E[N];

int head[N],d[N],cnt;

char s[35],t[35],x[35],y[35];

inline void add(const int &s,const int &t,const int &dis)

{

	E[cnt].to=t;

	E[cnt].dx=dis;

	E[cnt].pre=head[s];

	head[s]=cnt++;

}

inline int hash_fun(char s[])

{

	int r=0,len=strlen(s);

	for (int i=0; i<len; i++)

	{

		r=r*17+s[i];

		r%=20023;

	}

	return r%20023;

}

inline void init()

{

	memset(head,-1,sizeof(head));

	MMINF(d);

	cnt=0;

}

inline void spfa(int s)

{

	typedef pair<int,int> pii;

	priority_queue<pii>Q;

	d[s]=0;

	Q.push(pii(-d[s],s));

	while (!Q.empty())

	{

		int now=Q.top().second;

		Q.pop();

		for (int i=head[now]; i!=-1; i=E[i].pre)

		{

			int v=E[i].to;

			int w=E[i].dx;

			if(d[v]>d[now]+w)

			{

				d[v]=d[now]+w;

				Q.push(pii(-d[v],v));

			}

		}

	}

}

int main(void)

{

	int n,i,z;

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

	{

		init();

		scanf("%s%s",s,t);

		int sta=hash_fun(s),des=hash_fun(t);

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

		{

			scanf("%s %s %d",x,y,&z);

			int S=hash_fun(x),T=hash_fun(y);

			add(S,T,z);

			add(T,S,z);

		}

		spfa(sta);

		d[des]==INF?puts("-1"):printf("%d\n",d[des]);

	}

	return 0;

}

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define INF 0x3f3f3f3f

#define MM(x) memset(x,0,sizeof(x))

#define MMINF(x) memset(x,INF,sizeof(x))

using namespace std;

typedef long long LL;

const int N=20100;

struct info

{

    int to;

    int dx;

    int pre;

}E[N];

int head[N],d[N],cnt;

char s[50],t[50],x[50],y[50];

void add(int s,int t,int dis)

{

    E[cnt].to=t;

    E[cnt].dx=dis;

    E[cnt].pre=head[s];

    head[s]=cnt++;

}

void init()

{

    memset(head,-1,sizeof(head));

    memset(d,INF,sizeof(d));

    cnt=0;

    MM(E);

}

void spfa(int s)

{

    typedef pair<int,int> pii;

    priority_queue<pair<int,int> >Q;

    d[s]=0;

    Q.push(pii(-d[s],s));

    while (!Q.empty())

    {

        int now=Q.top().second;

        Q.pop();

        for (int i=head[now]; i!=-1; i=E[i].pre)

        {

            int v=E[i].to;

            int w=E[i].dx;

            if(d[v]>d[now]+w)

            {

                d[v]=d[now]+w;

                Q.push(pii(-d[v],v));

            }

        }

    }

}

int main(void)

{

    int n,i,j,z,cnt_e;

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

    {

        init();

        cnt_e=0;

        map<string,int>pos;

        scanf("%s%s",s,t);

            pos[s]=++cnt_e;

        if(pos[t]==0)

            pos[t]=++cnt_e;

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

        {

            scanf("%s%s%d",x,y,&z);

            if(pos[x]==0)

                pos[x]=++cnt_e;

            if(pos[y]==0)

                pos[y]=++cnt_e;

            add(pos[x],pos[y],z);

            add(pos[y],pos[x],z);

        }

        spfa(pos[s]);

        if(d[pos[t]]==INF)

            puts("-1");

        else

            printf("%d\n",d[pos[t]]);

    }

    return 0;

}