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