【解题报告】HDU 1874 畅通工程续 -- Dijkstra算法详解 单源点最短路问题

此题Dijkstra算法，一次AC。这个算法时间复杂度O(n ²)附上该算法的演示图（来自 维基百科）：
附上：   迪科斯彻算法分解(优酷)
problem link -> HDU 1874

// HDU 1874 畅通工程续 -- 单源点最短路问题
// 邻接矩阵 + Dijkstra
// N 个村庄如果连通
// 最少拥有 N-1 条道路, 最多拥有 N(N-1)/2条道路
// 前提是任何两个村庄之间最多一条直达通道,但这个题目却有重复输入
/* test data
12 14
1 3 1
5 1 4
5 8 3
8 2 6
8 4 3
5 4 1
3 9 5
9 10 2
9 7 7
6 3 4
6 4 4
4 7 5
10 7 3
5 6 2
1 4
=5
3 3
0 1 1
0 2 3
1 2 1
0 2
=2
3 1
0 1 1
1 2
=-1
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int infinite = (1<<30); // 定义正无穷大(不能定义为((1<<31)-1)因为再相加会溢出) （~正无穷大 == 负无穷大）
const int MAXV = 101; // 村庄最多的个数
int via[MAXV][MAXV]; // 邻接矩阵
int n_villages,n_vias;
int d[MAXV]; // 源点S 距 点Pi的距离=d[i]
bool flag[MAXV]; // 标记不找回头路
int Dijkstra(int s,int e,int n){ // 最终结果 即最短路程 若不存在则-1
int min1 = s,min2 = 0; // via 的权值min1初始为0
for (int i = 0; i < MAXV ;i++)	d[i] = infinite;
while(min1 != e && min1 != infinite){// 找到了终点或者是找遍了整个集合
flag[min1] = true;
int temp1=infinite,temp2=infinite;
for (int i = 0; i < n; i++ ){
if (flag[i]) continue;
if (min2 + via[i][min1]
< d[i]){
d[i] = min2 + via[i][min1];
}
if (temp2 > d[i]){
temp2 = d[i];
temp1 = i;
}
}
min2 = temp2; min1 = temp1;
}
return (d[e] == infinite) ? (-1) : (d[e]);
}
void init(){
for (int i = 0 ; i < MAXV; i++){
for (int j = 0; j < MAXV ;j++)
via[i][j] = infinite;
flag[i] = false;
}
for (int i = 0; i < n_vias; i++){
int a,b,d;
scanf("%d%d%d",&a,&b,&d);
if (via[a][b] > d){ // 排除输入重复的边
via[a][b] = d;
via[b][a] = d;
}
}
}
int main()
{
freopen("in.txt","r",stdin);
while( scanf("%d%d",&n_villages,&n_vias) != EOF ){
init(); // 初始化 + 输入
int start,end;
scanf("%d%d",&start,&end);
if (start == end) {cout << "0" << endl;continue;} // 起点终点相同
cout << Dijkstra(start,end,n_villages) << endl;
}
return 0;
}

最后

以上就是开心战斗机为你收集整理的【解题报告】HDU 1874 畅通工程续 -- Dijkstra算法详解 单源点最短路问题的全部内容，希望文章能够帮你解决【解题报告】HDU 1874 畅通工程续 -- Dijkstra算法详解 单源点最短路问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。