首页 > 代码库 > hdu 2544 最短路 解题报告

hdu 2544 最短路 解题报告

2024-07-04 16:38:04   228人阅读

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

题目意思：给出 n 个路口和 m 条路，每一条路需要 c 分钟走过。问从路口 1 到路口 n 需要的最短时间是多少。

      这题是最短路的入门题，从理解d-i--j---k（wg自创的，呵呵）到默打到修改，搞左两日终于好了，哈哈哈~~~太感动了。

     第一次错是 少了Dijkstra()函数中的 for (j = 1; j <= n; j++) 。

     第二次错是把vis[k=j]=1 写在了 if (!vis[j] && dist[j] < mini) 里面。

     好好总结自己的错误，以后应该能避免了。（做完郑多燕后，灵感翻来了，成日系实验室里对住堆恶心的实验报告兼做5成功，有种令人想死的感觉，忽略忽略）

     顺便帮大家普及下科学知识，经过我的搜罗，

   dijkstra /?d??kstra/

      别读成 d  - i - j -k 了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 #define INF 100000000
 8 const int maxn = 100 + 10;
 9 int dist[maxn], map[maxn][maxn], vis[maxn];
10 int n, m;
11 
12 void Init()
13 {
14     int i, j, st, en, cost;
15     for (i = 1; i <= n; i++)
16         dist[i] = (i == 1 ? 0 : INF);
17     memset(vis, 0, sizeof(vis));
18     for (i = 1; i <= n; i++)
19     {
20         for (j = 1; j <= n; j++)
21             map[i][j] = INF;  // 这样也行：map[i][j] = map[j][i] = (i == j ? 0 : INF);
22     }
23     for (i = 1; i <= m; i++)
24     {
25         scanf("%d%d%d", &st, &en, &cost);
26         map[st][en] = map[en][st] = cost;   // 建立邻接矩阵
27     }
28 }
29 
30 void Dijkstra()
31 {
32     int i, j, k, mini;
33     for (i = 1; i <= n; i++)
34     {
35         mini = INF;
36         for (j = 1; j <= n; j++)   // 这个循环是用来找出与第i个点最近的点（当然是直接有边相连）
37         {
38             if (!vis[j] && dist[j] < mini)
39             {
40                 mini = dist[j];
41                 k = j;
42             }
43         }
44         vis[k] = 1;     // 如果把这句放在上面的if里面，就会把有些不该被标记已经过的点置1了，实质只需要置距离i点最短的那个点
45         for (j = 1; j <= n; j++)
46         {
47             if (dist[j] > mini + map[k][j])   // mini其实就是dist[k],mini + map[k][j]表示绕过k点走到j点的路径会不会比直接不绕过k要短
48                 dist[j] = mini + map[k][j];  // dist[j] = dist[k]+ map[k][j;
49         }
50     }
51 }
52 
53 int main()
54 {
55     while(scanf("%d%d", &n, &m) && (m || n))
56     {
57         Init();
58         Dijkstra();
59         printf("%d\n", dist[n]);
60     }
61     return 0;
62 }

 

    

     


联系
我们