HDU Today

经过锦囊相助，海东集团终于度过了危机，从此，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


虽然偶尔会迷路，但是因为有了你的帮助
**和**从此还是过上了幸福的生活。

――全剧终――
#include<stdio.h>
#include<cstring>
#include<string>
#include<map>

#define INF 0x3f3f3f3f
#define MAX 155
using namespace std;

int p[MAX][MAX];//邻接矩阵，存放距离 
int vis[MAX],dis[MAX];
//vis数组用于存放已经是最短时间的点
//dis数组用于存放从出发点到i点所花的最少时间 
int N; //公交车的总数 

int Dijkstra(int s,int n){//s为出发点，n为有多少条线路 
	for(int i = 1;i<=n;i++){//初始化 
		dis[i]=p[s][i];
		vis[i]=0;
	}
	//起点到自己的距离为0，vis集合中只有起点 
	dis[1]=0;
	vis[1]=1;
	
	for(int i = 1;i<=n;i++){
    	int k = -1;
		int temp=INF;
    	for(int j = 1;j<=n;j++)
        	if(!vis[j]&&dis[j]<temp){
        		temp=dis[j];
        		k=j;
        	} 
				
        if(k == -1) break;//没有找到一条小于INF的边，说明此时集合vis和非vis集合不连通 
        vis[k]=1; //将点k纳入集合vis中 
        for(int j = 1;j<=n;j++)//更新dis数组，dis[i]表示起点到i点的最短距离 
            if(!vis[j]&&dis[j]>dis[k]+p[k][j])
            	dis[j]=dis[k]+p[k][j];
    }
    return dis[2];//返回到达终点，存储在mp<终点,2> 
}

int main(){
    int t;
    char s1[35],s2[35];
    bool flag;
    map<string,int> mp;
	//容器mp，键值对应，将字符串当键值-->与数字对应可以理解为就是给每一个地点编号 		 
    while(scanf("%d",&N)!=EOF&&N!=-1){//N为公交车的总数 
        mp.clear(); //清空 
    	for(int i = 1;i<=MAX;i++)
        	for(int j = 1;j<=MAX;j++)
            	p[i][j]=INF;
            	
        scanf("%s%s",s1,s2);//徐总的所在地s1，目的地s2 
        mp[s1] = 1;
        mp[s2] = 2;
         
        int count=3;//用于计数，类似指针效果 
        flag=0;//flag用来判断是否所在地与目的地相同 
        if(strcmp(s1,s2)==0) //徐总所在地与目的地同个地方 
			flag=1; 
         
		for(int i=1;i<=N;i++){
           scanf("%s%s%d",s1,s2,&t);
        	//如果以城市当做指针的mp中为0，则将其装入容器中 
			if(!mp[s1]) mp[s1]=count++;
        	if(!mp[s2]) mp[s2]=count++;
        	//无向图，两地的来回所花时间相同 
        	p[mp[s1]][mp[s2]]=p[mp[s2]][mp[s1]]=t;      
        }
        if(flag){//如果徐总所在地与目的相同，直接返回0 
			printf("0\n");
			continue;
		}
        Dijkstra(1,count);
        /*
		*  dis[2]存放的是s2(目的地)，如果目的地为INF，表示无法
		* 到达，返回-1;如果不是，则可以到达，返回dis[2] 
        */
		printf("%d\n",dis[2]==INF?-1:dis[2]);
	}
    return 0;
}