首页 > 代码库 > HDU2112HDU Today

HDU2112HDU Today

2024-07-17 12:44:41   231人阅读

HDU Today

Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14761    Accepted Submission(s): 3479


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
6xiasha westlakexiasha station 60xiasha ShoppingCenterofHangZhou 30station westlake 20ShoppingCenterofHangZhou supermarket 10xiasha supermarket 50supermarket westlake 10-1
 
 
 
注意：相同的起点跟终点输出0
 
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<map>#include<string>using namespace std;const int MX=1<<30;int road[160][160],pay[160],aaa;struct node{    int s;    int t;};int bfs(){    int min1=MX;    node a,b;    a.s=1;    a.t=0;    pay[a.s]=a.t;    queue<node>q;    q.push(a);//cout<<aaa<<endl;    while(!q.empty())    {        a=q.front();        q.pop();        for(int i=2;i<=aaa;i++)        {            if(road[a.s][i]!=MX)            {                b.s=i;                b.t=a.t+road[a.s][i];                if(b.t<pay[i])                {                    //cout<<a.s<<" *** "<<i<<endl;                    if(b.t<min1&&b.s==2)                    {                        min1=b.t;                    }                    pay[i]=b.t;                    q.push(b);                }            }        }    }    //cout<<min1<<endl;    if(min1==MX)    return -1;    return min1;}int main(){    int n;    while(scanf("%d",&n)!=EOF)    {        if(n==-1)break;        map<string,int>zm;        char a[40],b[40],c[40],d[40];        scanf("%s%s",c,d);        zm[c]=1;        zm[d]=2;        aaa=3;        int i,j,q;        for(i=1;i<160;i++)        {            for(j=1;j<160;j++)            {                road[i][j]=MX;            }            pay[i]=MX;        }        for(i=0;i<n;i++)        {            scanf("%s%s%d",a,b,&q);            if(zm[a]==0)                zm[a]=aaa++;            if(zm[b]==0)                zm[b]=aaa++;            if(road[zm[a]][zm[b]]>q)            {                road[zm[a]][zm[b]]=q;                road[zm[b]][zm[a]]=q;            }        }        /*for(i=1;i<aaa;i++)        {            for(j=1;j<aaa;j++)            {                if(road[i][j]==MX)                printf("0");                else                    printf("%d",road[i][j]/10);            }            printf("\n");        }*/        if(strcmp(c,d)==0)        {            printf("0\n");continue;        }        printf("%d\n",bfs());    }    return 0;}



 

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


 

Author
lgx

 


联系
我们