首页 > 代码库 > hdu 2112 HDU Today 解题报告

hdu 2112 HDU Today 解题报告

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2112

题目意思:又是求最短路的,不过结合埋字符串来考查。

     受之前1004 Let the Balloon Rise 学到用map 的解法做之后,有点蠢蠢欲动,当时见到要用字典树做有点吓坏了(之前看过下,非一般难理解,所以暂时放下了)。于是,死就死吧,硬住头皮用map做,反反复复修改终于过了。

     首先是memory limit exceeded,因为无读清题目意思,直接开10000 * 10000的数组= =。细心留意这句话:note:一组数据中地名数不会超过150个。表示150 * 150 的数组即可!!

     接着就一直wa了,原因:无把map 清空!注意注意啊,用 STL 的时候要特别注意。还有一个就是起点与终点重合应该输出0,不可达输出-1,否则输出结果。

     还有一个小细节,代码中的 l 不要贪方便写在    for (int i = 0; i < n; i++)   循环里面,因为出了这个循环之后,l 对其他部分是不可见的,默认变为0。而我们是需要 l 的值,因为它记录了每个站名依次对应的编号。

      呕心沥血版,新鲜出炉啊~~~~

     

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <string>  // 这个头文件不能缺,否则会CE
 6 #include <map>
 7 using namespace std;
 8 
 9 const int INF = 0xffffff;
10 const int maxn = 150 + 10;
11 int dist[maxn], grid[maxn][maxn], vis[maxn];
12 int n, l, cost, flag;
13 map<string, int> zhan;
14 
15 void Init()
16 {
17     memset(grid, 0, sizeof(grid));   // 这个也是关键,因为下面的if (!grid[i][j]) 要用到,表示无边直接相连的点的距离设为INF
18     zhan.clear();    // 关键关键!!!!
19     flag = 0, l = 3;
20     string tmp1, tmp2;
21     cin >> tmp1 >> tmp2;
22     if (tmp1 == tmp2)
23         flag = 1;
24     zhan[tmp1] = 1;   // 起点为1,终点为2
25     zhan[tmp2] = 2;
26     for (int i = 0; i < n; i++)   // 为每个站名编号
27     {
28         cin >> tmp1 >> tmp2 >> cost;
29         if (zhan[tmp1] == 0)
30         {
31             zhan[tmp1] = l;
32             l++;
33         }
34         if (zhan[tmp2] == 0)
35         {
36             zhan[tmp2] = l;
37             l++;
38         }
39         grid[zhan[tmp1]][zhan[tmp2]] = grid[zhan[tmp2]][zhan[tmp1]] = cost;
40     }
41     for (int i = 0; i < l; i++)
42     {
43         for (int j = 0; j < l; j++)
44         {
45             if (!grid[i][j])
46                 grid[i][j] = grid[j][i] = INF;
47         }
48     }
49     dist[1] = 0;   // 离自己的距离为0
50     for (int i = 2; i < l; i++)  // 求出其他站离它的距离是多少
51         dist[i] = grid[1][i];
52 }
53 
54 void Dijkstra()
55 {
56     memset(vis, 0, sizeof(vis));
57     for (int i = 1; i < l; i++)
58     {
59         int u;
60         int maxx = INF;
61         for (int j = 1; j < l; j++)
62         {
63             if (!vis[j] && dist[j] < maxx)
64                 maxx = dist[u = j];
65         }
66         vis[u] = 1;
67         for (int j = 1; j < l; j++)
68         {
69             if (dist[j] > dist[u] + grid[u][j])
70                 dist[j] = dist[u] + grid[u][j];
71         }
72     }
73     if (flag)   // 代表起点与终点重合!
74         printf("0\n");
75     else
76         printf("%d\n", dist[2] == INF ? -1 : dist[2]);
77 }
78 
79 int main()
80 {
81     while (scanf("%d", &n) && n != -1)  // n: 城市, m:道路
82     {
83         Init();
84         Dijkstra();
85     }
86     return 0;
87 }