Dijkstra算法 HDU 1874 畅通工程续

Dijkstra算法描述起来比较容易:它是求单源最短路径的,也就是求某一个点到其他各个点的最短路径,大体思想和prim算法差不多,有个数组dis,用来保存源点到其它各个点的距离,刚开始很好办,只需要把邻接矩阵里面它到其它点的距离复制过来就行了。剩下的步骤就是找到一个源点到其他点最小的距离,将它加入到已经确定下来的最短距离中,接着更新其他点到源点的距离,因为确定了一些点的最近距离之后,那么到其它未确定的点的距离可能会变小,所以更新一下。

理论完了 就要实践:http://acm.hdu.edu.cn/showproblem.php?pid=1874

AC代码:

技术分享
 1 #include<iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int N = 204;
 6 const int INFINITY = 999999999;
 7 int Map[N][N];
 8 void init(int n)
 9 {
10     for (int i = 0; i < n; i++)
11         for (int j = 0; j < n; j++)
12             Map[i][j] = INFINITY;
13 }
14 //v0代表源点,n是总数,dis数组表示到其他点的距离
15 void dijkstra(int v0, int n, int dis[])
16 {
17     //标记是否已经找到最短距离
18     bool Final[n];
19     memset(Final, false, sizeof(Final));
20     for (int i = 0; i < n; i++)
21         dis[i] = Map[v0][i];
22     dis[v0] = 0;
23     //源点已经找到
24     Final[v0] = true;
25     int min_dis;
26     for (int i = 1; i < n; i++)
27     {
28         min_dis = INFINITY;//找剩下的所有点中最小的一个
29         int k = 0;
30         for (int j = 0; j < n; j++)
31         {
32             if (!Final[j] && dis[j] < min_dis)
33             {
34                 min_dis = dis[j];
35                 k = j;
36             }
37         }
38         //如果最小的存在,就将它标记已经找到最短距离
39         if (min_dis < INFINITY)
40             Final[k] = true;
41         else
42             break;//如果找不到最小的,就是不连通图
43         for (int j = 0; j < n; j++)//更新其他点到它的距离
44         {
45             if (!Final[j] && min_dis + Map[k][j] < dis[j])
46             {
47                 dis[j] = min_dis + Map[k][j];
48             }
49         }
50     }
51 }
52 int main()
53 {
54     int n, m;
55     while (~scanf("%d %d", &n, &m))
56     {
57         init(n);
58         int a, b, x;
59         for (int i = 0; i < m; i++)
60         {
61             scanf("%d %d %d", &a, &b, &x);
62             //两个城市之间的道路可能有多条,取最小的那条
63             if (Map[a][b] > x)
64                 Map[a][b] = Map[b][a] = x;
65         }
66         int s, e;
67         scanf("%d %d", &s, &e);
68         int ans[n];
69         dijkstra(s, n, ans);
70         if (ans[e] < INFINITY)
71             printf("%d\n", ans[e]);
72         else
73             puts("-1");
74     }
75 
76 
77     return 0;
78 }
View Code

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。