HUD-2112 HDU Today（最短路map标记）

佚名 6年前 (2019-05-24) 算法 1361人围观抢沙发百度已收录

HDU Today

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

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

思路：

1.最短路spfa模板.

2.map标记建图.

3.考虑距离为0或者-1的情况.

总结：下次map记得清空orz。

AC代码：

 1 #include<cstdio>
 2 #include<map>
 3 #include<iostream>
 4 #include<queue>
 5 using namespace std;
 6 const int INF = 0x3f3f3f3f;
 7 const int maxn = 155;
 8 int Map[maxn][maxn];
 9 int n;
10 int d[maxn];
11 int vis[maxn];
12 void spfa(int s,int n)
13 {
14     queue<int> q;
15     for(int i = 1;i <= n;i++)
16     {
17         d[i] = INF;
18         vis[i] = 0;
19     }
20     d[s] = 0;
21     vis[s] = 1;
22     q.push(s);
23     while(!q.empty())
24     {
25         int k = q.front();q.pop();
26         vis[k] = 0;
27         for(int j = 1;j <= n;j++)
28         {
29             if(d[k] + Map[k][j] < d[j])
30             {
31                 d[j] = d[k] + Map[k][j];
32                 if(!vis[j])
33                     q.push(j),vis[j] = 1;
34             }
35         }
36     }
37 }
38 void init()
39 {
40     for(int i = 0;i <= 150;i++)
41     {
42         for(int j = 0;j <= i;j++)
43         {
44             if(j != i)
45             Map[i][j] = Map[j][i] = INF;
46             else Map[i][j] = 0;
47         }
48     }
49 }
50 int main()
51 {
52     char a[50],b[50];
53     map<string,int> mp;
54     char st[50],ed[50];
55     int w;
56     while(~scanf("%d",&n) && n!= -1)
57     {
58         init();//初始化
59         mp.clear();
60         int count = 0;//用于map一对一转化；
61         scanf("%s%s",&a,&b);
62         mp[a] = ++count;
63         if(!mp[b]) mp[b] = ++count;//如果终点未出现过，则加入图中；
64         for(int i = 0;i < n;i++)
65         {
66             scanf("%s %s %d",&st,&ed,&w);
67             if(!mp[st]) mp[st] = ++count;//检查两点是否出现过
68             if(!mp[ed]) mp[ed] = ++count;
69             int u = mp[st],v = mp[ed];
70             Map[u][v] = Map[v][u] = w;//建图;
71         }
72         spfa(1,count);
73         if(d[ mp[b] ] == INF) printf("-1\n");
74         else printf("%d\n",d[ mp[b] ]);
75     }
76     return 0;
77 }