[HDU - 1874] 畅通工程续

发表于 | 更新于 | 分类于 ， ，
本文字数： 8.9k

链接

\(\text{HDU - 1874}\)

题意

  共\(\text{n}\)个城市，给出\(\text{m}\)个城市间的关系，即两个城市间的距离，现在给你一个起点和终点，需要你求出两个城市的最短路径。

分析

  求单源最短路径，这里给出\(\text{Dijkstra}\)和\(\text{Bellman_ford}\)算法的两种实现模板。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<queue>
#include<string>
#define INF (int)1e9+7
using namespace std;
int n,m,x,s,t,u,v,in;
//dis存储最短距离，book用来标记某一点是否已确定其最短路径并存入dis里，cost存储两点是否有边及边的权值
int dis[205],book[205],cost[205][205];
//初始化dis与book
void init() {
	for (int i = 0; i <=200; i++) {
		dis[i] = INF;
	}
	for (int i = 0; i <=200; i++) {
		book[i] = 0;
	}
}
//从s出发到其他所有点的最短路径
void Dijkstra(int s) {
	init();
	dis[s] = 0;
	in = 0;
	while (true) {
		int minn = INF;
		for (int i = 0; i < n; i++) {
			if (!book[i] && minn > dis[i]) {
				minn = dis[i];
				in=i;
			}
		}
		//如果没有更新，说明全部点的最短路已找到并保存
		if (minn == INF)
			break;
		//book[in]=1来标记in这个点的最短路径已找到并存在DIS[I]里
		book[in] = 1;
		for (int i = 0; i < n; i++) {
			//如果dis[i]没有被确定保存的已是最短路径并且I与in之间存在边连接并且可已更新dis数组
			if (!book[i] &&cost[i][in]!=INF&& dis[i] >dis[in] + cost[i][in]) {
				dis[i] = dis[in] + cost[i][in];
			}
		}
	}
}
int main() {
	while (scanf("%d%d",&n,&m)!=EOF) {
		//需要将cost初始化
		for (int i = 0; i <= 200; i++)
			for (int j = 0; j <= 200; j++)
				cost[i][j] = INF;
		for (int i = 0; i < m; i++) {
			cin >> u>>v>>x;
			if(cost[u][v]>x)
				cost[v][u] = cost[u][v]=x;

		}
		cin >> s >> t;
		Dijkstra(s);
		cout << (dis[t] == INF ? -1 : dis[t] )<< endl;
	}
	return 0;
}