HDU Today
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 13235 Accepted Submission(s): 3096
Problem Description
经过锦囊相助，海东集团终于度过了危机，从此，HDU的发展就一直顺风顺水，到了2050年，集团已经相当规模了，据说进入了钱江肉丝经济开发区500强。这时候，XHD夫妇也退居了二线，并在风景秀美的诸暨市浬浦镇陶姚村买了个房子，开始安度晚年了。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“Can you help me?”。看着他那迷茫而又无助的眼神，热心的你能帮帮他吗？
请帮助他用最短的时间到达目的地（假设每一路公交车都只在起点站和终点站停，而且随时都会开）。
这样住了一段时间，徐总对当地的交通还是不太了解。有时很郁闷，想去一个地方又不知道应该乘什么公交车，在什么地方转车，在什么地方下车（其实徐总自己有车，却一定要与民同乐，这就是徐总的性格）。
徐总经常会问蹩脚的英文问路：“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，表示输入结束。
第二行有徐总的所在地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"string.h"
#define N 155
#define M 35
const int inf=10000000;
int g[N][N];
int min(int a,int b)
{
return a<b?a:b;
}
void dijkstra(int s,int e,int n)
{
int i,index,min;
int mark[N],dis[N];
memset(mark,0,sizeof(mark));
mark[s]=1;
for(i=0;i<n;i++)
dis[i]=g[s][i];
while(1)
{
index=-1;
min=inf;
for(i=0;i<n;i++)
{
if(!mark[i]&&min>dis[i])
{
index=i;
min=dis[i];
}
}
if(index==-1||index==e)
break;
mark[index]=1;
for(i=0;i<n;i++)
{
if(!mark[i]&&dis[i]>dis[index]+g[index][i])
{
dis[i]=dis[index]+g[index][i];
}
}
}
if(dis[e]<inf)
printf("%d\n",dis[e]);
else
printf("-1\n");
}
int main()
{
int i,j,t,n,m;
char str[N][M],s[M],e[M];
while(scanf("%d",&n),n!=-1)
{
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
g[i][j]=inf;
}
}
scanf("%s %s",str[0],str[1]);
m=2;
int a,b;
for(i=0;i<n;i++)
{
scanf("%s %s %d",s,e,&t);
for(j=0;j<m;j++)
{
if(strcmp(str[j],s)==0)
{
a=j;
break;
}
}
if(j==m)
{
a=j;
strcpy(str[j],s);
m++;
}
for(j=0;j<m;j++)
{
if(strcmp(str[j],e)==0)
{
b=j;
break;
}
}
if(j==m)
{
b=j;
strcpy(str[j],e);
m++;
}
g[a][b]=g[b][a]=t;
}
if(strcmp(str[0],str[1])==0)
{
printf("0\n");
continue;
}
dijkstra(0,1,m);
}
return 0;
}