题解 | 畅通工程续

题目链接

思路：考察单源最短路径，用Dijkstra算法：BFS遍历+贪心算法

1.先定义距离数组，记录所有点到起点的距离，初始正无穷

2.BFS：取出起点，（如果更小）更新邻居到起点的距离(利用小根堆--优先队列结构实现）

3.贪心：取出离结点最近的点，设为新起点，执行2

#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;

struct Edge {
	int u;
	int v;
	int w;
	Edge(int u_, int v_, int w_) {
		u = u_;
		v = v_;
		w = w_;
	}
};

struct PQ {
	int num;//结点编号
	int distance;//到起点距离
	PQ(int num_, int distance_) {
		num = num_;
		distance = distance_;
	}
};
bool operator <(PQ l, PQ r) {
	if (l.distance> r.distance) {
		return true;
	}
	else {
		return false;
	}
}

vector<Edge> vec[201];//邻接表的顶点数组
//计算S-T的单源最短路径
int Dijkstra(int S, int T) {
	//小根堆排序
	priority_queue<PQ> Q;
	int distance[201];
	int visited[201];
	//1.先定义距离数组，记录所有点到起点的距离，初始-1为正无穷
	for (int i = 0; i < 201; i++) {
		distance[i] = -1;
		visited[i] = 0;
	}
	distance[S] = 0;//起点到起点距离
	PQ qnode(S, 0);
	Q.push(qnode);
	while (!Q.empty()) {
		int u = Q.top().num;
		Q.pop();
		if (visited[u] != 0) {//避免重复访问
			continue;
		}else {
			visited[u] = 1;
			//2.BFS遍历u点邻居（vec[u]数组），更新u到v距离
			for (int i = 0; i < vec[u].size(); i++) {
				int v = vec[u][i].v;
				int w = vec[u][i].w;
				if (distance[v] == -1 || distance[v] > distance[u] + w) {
					distance[v] = distance[u] + w;
					//更新小根堆
					PQ qnode1(v, distance[v]);
					Q.push(qnode1);
				}
			}
		}
	}
	return distance[T];
}

int main() {
	int N, M,a,b,w;
	while (scanf("%d%d", &N, &M) != EOF) {
		for (int i = 0; i < N; i++) {
			vec[i].clear();//每次循环前把数组清空
		}
		for (int i = 0; i < M; i++) {
			scanf("%d%d%d", &a, &b, &w);
			//双向道路
			Edge e1(a, b, w);
			vec[a].push_back(e1);
			Edge e2(b, a, w);
			vec[b].push_back(e2);
		}
		int S, T;
		scanf("%d%d", &S, &T);
		printf("%d\n", Dijkstra(S, T));
	}
	return 0;
}