首页 > 代码库 > ACM2112迪克斯特算法
ACM2112迪克斯特算法
HDU Today
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
6xiasha westlakexiasha station 60xiasha ShoppingCenterofHangZhou 30station westlake 20ShoppingCenterofHangZhou supermarket 10xiasha supermarket 50supermarket westlake 10-1
Sample Output
50
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\n");139 continue;140 }141 if(strcmp(kep1,kep2)==0)142 {143 printf("0\n");144 continue;145 }146 int result=bus.Dijkstra(a,b);147 printf("%d\n",result);148 }149 return 0;150 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。