题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2112

 

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


 

6 xiasha westlake xiasha station 60 xiasha ShoppingCenterofHangZhou 30 station westlake 20 ShoppingCenterofHangZhou supermarket 10 xiasha supermarket 50 supermarket westlake 10 -1

 

 

Sample Output


 

50 Hint: The best route is: xiasha->ShoppingCenterofHangZhou->supermarket->westlake 虽然偶尔会迷路，但是因为有了你的帮助 **和**从此还是过上了幸福的生活。 ――全剧终――

这道题还是最短路问题，但是输入的是字符，而不是数字，因此我们要用数字代表车站，可以用结构体，这里我用的是map函数，他本身代有一一映射的关心，把字符设置成主要的，后面设置一个int与之对应：

比如map<string,int>  bus;bus是名字，随意起；

当然结构体也行，但这个我觉得更方便一点，就学了一下map的应用，其实他我觉得也是个结构体：

#include<stdio.h>
#include<string.h>
#include<math.h>

#include<map>
#include<queue>
#include<stack>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

#define ll long long
#define da    0x3f3f3f3f
#define xiao -0x3f3f3f3f
#define clean(a,b) memset(a,b,sizeof(a))


int shuzu[200][200];
bool biaoji[200];
int shuaxin[200];
int n,k; 

void prime(int x)				//每一个车站都有着对应的数字，所以有转换成了之前的 
{
	int i,j;
	clean(biaoji,0);
	clean(shuaxin,da);
	shuaxin[x]=0;
	for(i=0;i<n;++i)
	{
		int can=-1;
		int min=da;
		for(j=1;j<=k;++j)
		{
			if(shuaxin[j]<min&&biaoji[j]==0)
			{
				min=shuaxin[j];
				can=j;
			}
		}
		if(can==-1)
			break;
		biaoji[can]=1;
		for(j=1;j<=k;++j)
		{
			if(biaoji[j]==0&&shuaxin[j]>shuaxin[can]+shuzu[can][j])
				shuaxin[j]=shuaxin[can]+shuzu[can][j];
		}
	}
}


int main()
{
	map<string,int> bus;
	while(~scanf("%d",&n))
	{
		if(n==-1)
			break;
		int i,j;
		for(i=0;i<200;++i)
		{
			for(j=0;j<200;++j)
				shuzu[i][j]=da;				//初始化没有路线 
		}
		bus.clear();						//清空map 
		string s,e;
		cin>>s>>e;							//输入起始点和目的地 
		bus[s]=1;							//将之设为1和2 
		bus[e]=2;
		
		k=3;								//从第三个开始 
		for(i=0;i<n;++i)
		{
			string s1,s2;
			int l;
			cin>>s1>>s2>>l;					//输入公交线路 
			if(bus[s1]==0)					//如果这个线路没出现过 
				bus[s1]=k++;				//映射一个int数 
			if(bus[s2]==0)					//第二个站 
				bus[s2]=k++;
			if(shuzu[bus[s1]][bus[s2]]>l)	//如果这个车的时间在这条路线上最短 
			{
				shuzu[bus[s1]][bus[s2]]=l;	//双向连通图 
				shuzu[bus[s2]][bus[s1]]=l;	// 
			}
		}
		if(s==e)							//如果起始点和目的地一样就只需要0时间 
		{
			printf("0\n");
			continue;						//结束此次查找 
		}
		prime(1);							//1是初始地，从这里开始找 
		if(shuaxin[bus[e]]<da)
			printf("%d\n",shuaxin[bus[e]]);	//有路线输出 
		else
			printf("-1\n");					//到不了 
	}
}