???http://acm.hdu.edu.cn/showproblem.php?pid=2112
怎樣把具體的字母的地點轉換為數字的函數為題目的重點。
???????????????????????? HDU Today
Time Limit: 15000/5000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11385????Accepted Submission(s): 2663
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
50
Hint:
The best route is: xiasha->ShoppingCenterofHangZhou->supermarket->westlake
雖然偶爾會迷路，但是因為有了你的幫助 **和**從此還是過上了幸福的生活。
――全劇終――
Author
lgx
Source
ACM程序設計_期末考試（時間已定！！）
Recommend
lcy
這是我參考別人的代碼過的：
1 #include<stdio.h> 2 #include<string.h> 3 #define maxint 0xfffffff 4 int map[160][160], visited[160], n, m, s, e; 5 long dis[160]; 6 char name[160][32]; 7 int find(char str[32]) 8 { 9 int i; 10 for(i = 1; i <= m; ++i){ 11 if(strcmp(name[i], str) == 0) 12 return i; 13 } 14 if(m == 0 || i > m){ 15 ++m; 16 strcpy(name[m], str); 17 return m; 18 } 19 }//函數的寫法。 20 void dijkstra(int s, int e) 21 { 22 int i, j, mid; 23 for(i = 1; i <= m; i++) 24 { 25 dis[i] = map[s][i]; 26 visited[i] = i == s ? 1 : 0; 27 } 28 for(i = 1; i <= m - 1; i++) 29 { 30 mid = 0; 31 dis[mid] = maxint; 32 for(j = 1; j <= m; j++) 33 if(!visited[j] && dis[j] < dis[mid]) 34 mid = j; 35 visited[mid] = 1; 36 for(j = 1; j <= m; j++) 37 if(map[mid][j] < maxint && !visited[j] && map[mid][j] + dis[mid] < dis[j]) 38 dis[j] = map[mid][j] + dis[mid]; 39 } 40 } 41 int main() 42 { 43 int i, j, a, b, c; 44 char s1[40], s2[40], start[40], end[40]; 45 scanf("%d", &n); 46 while(n != -1) 47 { 48 m = 0; 49 for(i = 1; i <= 140; ++i){ 50 for(j = 1; j <= 140; j++) 51 map[i][j] = maxint; 52 } 53 scanf("%s %s", start, end); 54 for(i = 1; i <= n; i++) 55 { 56 scanf("%s %s %d", s1, s2, &c); 57 a = find(s1); 58 b = find(s2); 59 if(map[a][b] > c) 60 { 61 map[a][b] = c; 62 map[b][a] = c; 63 } 64 } 65 s = find(start); 66 e = find(end); 67 if(s == e) 68 printf("0\n"); 69 else{ 70 dijkstra(s, e); 71 if(dis[e] != maxint) 72 printf("%ld\n", dis[e]); 73 else 74 printf("-1\n"); 75 } 76 scanf("%d", &n); 77 } 78 return 0; 79 }
?但是我原先自己寫的倆個算法怎么也過不了，我不知道是什么原因：要找出來。。。
1 #include<stdio.h> 2 #include<string.h> 3 #define Max 0xfffffff 4 int map[160][160],mark[160]; 5 int n,m,s,e; 6 long f[160]; 7 char name[160][32]; 8 int find(char str[30]) 9 { 10 int i; 11 for(i=1;i<=m;i++) 12 { 13 if(strcmp(name[i],str)==0) 14 return i; 15 } 16 if(m==0||i>m) 17 { 18 ++m; 19 strcpy(name[m],str); 20 21 return m; 22 } 23 } 24 int min(int x,int y) 25 { 26 return x>y?y:x; 27 } 28 void getmap() 29 { 30 int a,b,i,j,l; 31 char s1[40],s2[40]; 32 for(i=0;i<=140;i++) 33 for(j=0;j<=140;j++) 34 map[i][j]=(i==j?0:Max); 35 for(i=0;i<n;i++) 36 { 37 scanf("%s%s%d",&s1,&s2,&l); 38 a=find(s1); 39 b=find(s2); 40 map[a-1][b-1]=map[b-1][a-1]=min(map[a-1][b-1],l); 41 } 42 } 43 void dijkstra() 44 { 45 int i,j,k,min; 46 memset(mark,0,sizeof(mark)); 47 for(i=0;i<n;i++) 48 f[i]=map[s][i]; 49 f[s]=0; 50 for(i=0;i<n;i++) 51 { 52 min=Max; 53 for(j=0;j<n;j++) 54 { 55 if(!mark[j]&&min>f[j]) 56 { 57 k=j; 58 min=f[j]; 59 } 60 } 61 if(min==Max)break; 62 mark[k]=1; 63 for(j=0;j<n;j++) 64 if(!mark[j]&&f[j]>f[k]+map[k][j]) 65 f[j]=map[k][j]+f[k]; 66 } 67 if(f[e]!=Max) printf("%ld\n",f[e]); 68 else printf("-1\n"); 69 } 70 71 int main() 72 { 73 while(~scanf("%d",&n)&&n>0) 74 { 75 if(n==-1) 76 break; 77 char start[40],end[40]; 78 scanf("%s%s",start,end); 79 s=find(start)-1; 80 e=find(end)-1; 81 getmap(); 82 if(s==e) 83 printf("0\n"); 84 else 85 dijkstra(); 86 87 } 88 return 0; 89 }
1 #include<stdio.h> 2 #include<string.h> 3 #define Max 0xfffffff 4 int n,m,s,e,map[160][160]; 5 char name[160][32]; 6 int find(char str[30]) 7 { 8 int i; 9 for(i=1;i<=m;i++) 10 { 11 if(strcmp(name[i],str)==0) 12 return i; 13 } 14 if(m==0||i>m) 15 { 16 ++m; 17 strcpy(name[m],str); 18 19 return m; 20 } 21 } 22 int min(int x,int y) 23 { 24 return x>y?y:x; 25 } 26 void getmap() 27 { 28 int a,b,i,j,l; 29 char s1[40],s2[40]; 30 for(i=0;i<n;i++) 31 for(j=0;j<n;j++) 32 map[i][j]=(i==j?0:Max); 33 for(i=0;i<n;i++) 34 { 35 scanf("%s%s%d",&s1,&s2,&l); 36 a=find(s1); 37 b=find(s2); 38 map[a-1][b-1]=map[b-1][a-1]=min(map[a-1][b-1],l); 39 } 40 } 41 void floyd(int s,int e) 42 { 43 int i,j,k; 44 for(k=0;k<n;k++) 45 for(i=0;i<n;i++) 46 for(j=0;j<n;j++) 47 map[i][j]=min(map[i][j],map[i][k]+map[k][j]); 48 printf("%d\n",map[s][e]<Max?map[s][e]:-1); 49 50 } 51 int main() 52 { 53 while(~scanf("%d",&n)&&n>0) 54 { 55 if(n==-1) 56 break; 57 char start[40],end[40]; 58 scanf("%s%s",start,end); 59 s=find(start)-1; 60 e=find(end)-1; 61 getmap(); 62 floyd(s,e); 63 64 } 65 return 0; 66 }
?再次重新做這個題目寫的代碼ac：
?
#include<stdio.h>
#include<string.h>
#define INF 0xfffffff
int m,map[2600][2600],mark[2600];
int n,s,e;
long f[2600];
char name[2600][32];
int find(char str[32])
{int i;for(i=0;i<m;i++){if(strcmp(str,name[i])==0)return i;}if(m==0||i==m){strcpy(name[i],str);m++;return i;}
}
void dijkstra(){int i,j,k,min;memset(mark,0,sizeof(mark));for(i=0;i<n;i++)f[i]=map[s][i];f[s]=0;for(i=0;i<m;i++){min=INF;for(j=0;j<m;j++){if(!mark[j]&&min>f[j]){k=j;min=f[j];}}if(min==INF)break;mark[k]=1;for(j=0;j<n;j++)if(!mark[j]&&f[j]>f[k]+map[k][j])f[j]=map[k][j]+f[k];}if(f[e]!=INF) printf("%ld\n",f[e]);else printf("-1\n");}int main(){int i,j,x,y,time;while(~scanf("%d",&n)&&n!=-1){ m=0;char start[50],end[50],from[50],to[50];scanf("%s%s",start,end);s=find(start);e=find(end);for(i=0;i<160;i++)for(j=0;j<160;j++)if(i==j)map[i][j]=map[j][i]=0;elsemap[i][j]=map[j][i]=INF;for(i=0;i<n;i++){scanf("%s%s%d",from,to,&time);x=find(from);y=find(to);map[x][y]=map[y][x]=time;}if(s==e)printf("0\n");elsedijkstra();}return 0;}?
