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++ ){  //以 [0]-- 1 ---  [1]  为例;一开始标记了flag[0]=true so跳过

			if (flag[i]) continue;     //     |			  |    //找到via[1][min1(此时为0)]发现比较小 数值先存起来

											//| 3--[2] --1|    //继续找via[2][0]发现比之前的大 不存

			if (min2 + via[i][min1]  < d[i]){        //把之前找到的那个较短值的点给min1(变成1)标记[1]为true

				d[i] = min2 + via[i][min1];        //现在我们要做的就是该点加上之前那个最小的权看会不会比 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; //初始化 标记数组为 每个点都是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算法详解 单源点最短路问题

最新文章

热门文章

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