ACM2112迪克斯特算法 HDU Today

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

  1 #include<iostream>
  2 #include<cstring>
  3 using namespace std;
  4 class Alphabet
  5 {
  6     public:
  7     char s[50];
  8     Alphabet *next;
  9     int index;
 10 };
 11 class BUS
 12 {
 13     public:
 14         BUS(int n)//number of bus and followed lines
 15         {
 16             cnt=1;
 17             oo=11111111;
 18             number=n;
 19             p=NULL;
 20             head=NULL;
 21             record=NULL;
 22             Continue=true;//控制Deal函数的作用，为真时是输入使用，为假时是判断是否存在七点和终点 
 23             memset(vis,0,sizeof(vis));
 24             for(int i=0;i<200;i++)
 25             for(int j=0;j<200;j++)
 26             maze[i][j]=oo;
 27         }
 28         ~BUS()
 29         {
 30             Alphabet *temp;
 31             while(head!=NULL)
 32             {
 33                 temp=head;
 34                 head=head->next;
 35                 delete temp;
 36             }
 37         }
 38         void Command(char *str1,char *str2,int distance)
 39         {
 40             int a=Deal(str1);
 41             int b=Deal(str2);
 42             if(maze[a][b]>distance)
 43             maze[a][b]=maze[b][a]=distance;
 44         }
 45         int Dijkstra(int s,int e)
 46         {
 47             int n=cnt-1;
 48             for(int i=1;i<=n;i++)
 49             low[i]=maze[s][i];
 50             low[s]=0;
 51             vis[s]=1;
 52             int v;
 53             for(int i=1;i<n;i++)
 54             {
 55                 int Min=oo;
 56                 for(int j=1;j<=n;j++)
 57                     if(!vis[j]&&low[j]<Min)
 58                     {
 59                         Min=low[j];
 60                         v=j;
 61                     }
 62                 if(Min==oo)return -1;
 63                 vis[v]=1;
 64                 for(int j=1;j<=n;j++)
 65                 {
 66                     if(!vis[j]&&low[j]>maze[v][j]+low[v])
 67                     low[j]=maze[v][j]+low[v];
 68                 }
 69             }
 70             return low[e];
 71         }
 72         int Deal(char *str)
 73         {
 74             int index=0;
 75             p=head;
 76             while(p!=NULL)
 77             {
 78                 if(strcmp(p->s,str)!=0)
 79                 {
 80                     record=p;
 81                     p=p->next;
 82                 }
 83                 else 
 84                 {
 85                     index=p->index;
 86                     break;
 87                 }
 88             }
 89             if(index==0&&Continue)
 90             return Insert(str);
 91              return index;
 92         }
 93         void ChangeContinue()
 94         {
 95             Continue=false;
 96         }
 97         int Insert(char *str)
 98         {
 99             Alphabet *temp;
100             temp=record;
101             p=new Alphabet;
102             strcpy(p->s,str);
103             p->index=cnt++;
104             p->next=NULL;
105             if(head==NULL)
106                 head=p;
107             else 
108             temp->next=p;
109             return p->index;
110         }
111     private:
112         int oo;
113         int cnt,number;
114         Alphabet *p,*head,*record;
115         int maze[200][200];
116         int low[200],vis[200];
117         bool Continue;
118 };
119 int main()
120 {
121     int n,a,b,dis;
122     char s1[50],kep1[50];
123     char s2[50],kep2[50];
124     while(cin>>n&&n!=-1)
125     {
126         BUS bus(n);
127         scanf("%s %s",kep1,kep2);
128         for(int i=1;i<=n;i++)
129         {
130             scanf("%s %s %d",s1,s2,&dis);
131             bus.Command(s1,s2,dis);
132         }
133         bus.ChangeContinue();
134         a=bus.Deal(kep1);
135         b=bus.Deal(kep2);
136         if(!a||!b)
137         {
138             printf("-1
");
139             continue;
140         }
141         if(strcmp(kep1,kep2)==0)
142         {
143             printf("0
");
144             continue;
145         }
146         int result=bus.Dijkstra(a,b);
147         printf("%d
",result);
148     }
149     return 0;
150 }

ACM2112迪克斯特算法 HDU Today

相关推荐