hdoj HDU Today

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

  
   

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

  
   

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

lgx

#include<cstdio>
#include<cstdlib>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
char str[155][35];
char s[35],e[35];
int N,st,en;
int map[155][155];
int dist[155],vis[155];
int getnext(int k){int u=-1,i,t;t=inf;for(i=0;i<k;++i){if(!vis[i]&&t>dist[i]){t=dist[i];u=i;}}return u;
}
int dijkstra(int k){int i,j,u=st,temp;memset(vis,0,sizeof(vis));vis[u]=1;while(u!=-1){for(i=0;i<k;++i){temp=dist[u]+map[u][i];if(temp<dist[i])dist[i]=temp;}vis[u]=1;if(vis[en])return dist[en];u=getnext(k);}return -1;
}
int main()
{int i,j,k;while(scanf("%d",&N)&&N!=-1){k=0;memset(map,0x3f,sizeof(map));scanf("%s %s",s,e);if(strcmp(s,e)!=0){st=k;strcpy(str[k++],s);en=k;strcpy(str[k++],e);}else {st=en=k;strcpy(str[k++],s);}int c;for(i=0;i<N;++i){scanf("%s %s %d",s,e,&c);int a=-1,b=-1;for(j=0;j<k;++j){if(strcmp(str[j],s)==0)a=j;if(strcmp(str[j],e)==0)b=j;}if(a==-1){a=k;strcpy(str[k++],s);}if(b==-1){b=k;strcpy(str[k++],e);}if(map[a][b]>c)map[a][b]=map[b][a]=c;}memset(dist,0x3f,sizeof(dist));dist[st]=0;printf("%d\n",dijkstra(k));}return 0;
}