hdu 2112 HDU Today HDU Today

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

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

xiasha westlake

xiasha station 60

xiasha ShoppingCenterofHangZhou 30

station westlake 20

ShoppingCenterofHangZhou supermarket 10

xiasha supermarket 50

supermarket westlake 10

-1

Sample Output

Hint:

The best route is:

xiasha->ShoppingCenterofHangZhou->supermarket->westlake

虽然偶尔会迷路，但是因为有了你的帮助

**和**从此还是过上了幸福的生活。

――全剧终――

Author

lgx

Source

ACM程序设计_期末考试（时间已定！！）

Recommend

lcy | We have carefully selected several similar problems for you: 2680 1142 1385 1690 2722

还是简单的最短路模板，不过这题输入的字符串，因此要将字符转化为整数数组存储，方便比较路程。

题意：中文题，很好理解。

附上代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #define M 160
 5 #define MAX 0x3f3f3f3f
 6 using namespace std;
 7 int m;
 8 int map[M][M],vis[M],dis[M];
 9 char place[M][35];
10 
11 int find(char s[])  //关键处理，将字符串数组转换为整数数组存储
12 {
13     int i;
14     for(i=1; i<=m; i++)
15     {
16         if(strcmp(s,place[i])==0)
17             return i;
18     }
19     strcpy(place[++m],s);
20     return m;
21 }
22 
23 int main()
24 {
25     int n,i,j,f,e;
26     char s[35];
27     while(~scanf("%d",&n))
28     {
29         if(n==-1) break;
30         m=0;
31         scanf("%s",s),f=find(s);
32         scanf("%s",s),e=find(s);
33         memset(vis,0,sizeof(vis));
34         memset(dis,0,sizeof(dis));
35         for(i=1; i<=150; i++)
36             for(j=1; j<=150; j++)
37             {
38                 if(i==j) map[i][j]=0;
39                 else     map[i][j]=MAX;
40             }
41         int a,b,c;
42         while(n--)
43         {
44             scanf("%s",s),a=find(s);
45             scanf("%s",s),b=find(s);
46             scanf("%d",&c);
47             if(map[a][b]>c)
48                 map[a][b]=c,map[b][a]=c;
49         }
50         vis[f]=1;
51         for(i=1; i<=m; i++)
52             dis[i]=map[f][i];
53         int min,t;
54         for(i=1; i<=m; i++)
55         {
56             min=MAX;
57             for(j=1; j<=m; j++)
58                 if(!vis[j]&&dis[j]<min)
59                 {
60                     min=dis[j];
61                     t=j;
62                 }
63             vis[t]=1;
64             for(j=1; j<=m; j++)
65                 if(!vis[j]&&map[t][j]<MAX)
66                     if(dis[j]>dis[t]+map[t][j])
67                         dis[j]=dis[t]+map[t][j];
68         }
69         if(dis[e]<MAX)
70             printf("%d
",dis[e]);
71         else
72             printf("-1
");
73     }
74     return 0;
75 }

邻接表：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #define M 10005
  6 #define N 155
  7 #define INF 0x3f3f3f3f
  8 #define ll long long
  9 using namespace std;
 10 int n,m,tol,s,t;
 11 struct Edge
 12 {
 13     int from,to,val;
 14     int next;
 15 }edge[M*2];
 16 int dis[N],head[M*2];
 17 bool vis[N];
 18 char place[N][35];
 19 
 20 int find(char s[])
 21 {
 22     for(int i=1;i<=m;i++)
 23     {
 24         if(strcmp(s,place[i])==0)
 25         return i;
 26     }
 27     strcpy(place[++m],s);
 28     return m;
 29 }
 30 
 31 void init()
 32 {
 33     tol=0;
 34     memset(head,-1,sizeof(head));
 35 }
 36 
 37 void addEdge(int u,int v,int val)
 38 {
 39     edge[tol].from=u;
 40     edge[tol].to=v;
 41     edge[tol].val=val;
 42     edge[tol].next=head[u];
 43     head[u]=tol++;
 44     edge[tol].from=v;
 45     edge[tol].to=u;
 46     edge[tol].val=val;
 47     edge[tol].next=head[v];
 48     head[v]=tol++;
 49 }
 50 
 51 void getmap()
 52 {
 53     char ss[35];
 54     scanf("%s",ss),s=find(ss);
 55     scanf("%s",ss),t=find(ss);
 56     int a,b,c;
 57     while(n--)
 58     {
 59         scanf("%s",ss),a=find(ss);
 60         scanf("%s",ss),b=find(ss);
 61         scanf("%d",&c);
 62         addEdge(a,b,c);
 63     }
 64     memset(dis,INF,sizeof(dis));
 65     memset(vis,false,sizeof(vis));
 66 }
 67 
 68 void spfa()
 69 {
 70     queue<int>q;
 71     q.push(s);
 72     vis[s]=true;
 73     dis[s]=0;
 74     while(!q.empty())
 75     {
 76         int u=q.front();
 77         q.pop();
 78         vis[u]=false;
 79         for(int i=head[u];i!=-1;i=edge[i].next)
 80         {
 81             int v=edge[i].to;
 82             if(dis[v]>dis[u]+edge[i].val)
 83             {
 84                 dis[v]=dis[u]+edge[i].val;
 85                 if(!vis[v])
 86                 {
 87                     vis[v]=true;
 88                     q.push(v);
 89                 }
 90             }
 91         }
 92     }
 93     if(dis[t]<INF)
 94     printf("%d
",dis[t]);
 95     else
 96     printf("-1
");
 97     return;
 98 }
 99 
100 int main()
101 {
102     while(~scanf("%d",&n))
103     {
104         if(n==-1) break;
105         init();
106         getmap();
107         spfa();
108     }
109     return 0;
110 }

hdu 2112 HDU Today HDU Today

相关推荐