数据结构与算法题目集7-35——城市间紧急救援

我的数据结构与算法题目集代码仓：https://github.com/617076674/Data-structure-and-algorithm-topic-set

原题链接：https://pintia.cn/problem-sets/15/problems/862

题目描述：

知识点：带权图的最短路径

思路：SPFA算法+深度优先遍历（回溯）

本题是PAT-ADVANCED1003——Emergency的中文版。

期望时间复杂度是O(kM)，其中k是一个常数，在很多情况下k不超过2，可见这个算法异常高效，并且经常性地优于堆优化的Dijkstra算法。

C++代码：

#include<iostream>
#include<queue>
#include<vector>
#include<set>

using namespace std;

struct node {
	int v, len;
	node(int _v, int _len) {
		v = _v;
		len = _len;
	}
};

int N, M, S, D, INF = 1000000000;
int teams[500], d[500], countInq[500];
vector<node> graph[500];
bool inq[500];
set<int> pre[500];
vector<int> tempPath, path;
int count = 0, maxTeams = 0;

bool spfa(int s);
void dfs(int nowVisit);

int main() {
	std::ios::sync_with_stdio(false);
	cin >> N >> M >> S >> D;
	for(int i = 0; i < N; i++) {
		cin >> teams[i];
	}
	for(int i = 0; i < M; i++) {
		int v1, v2, len;
		cin >> v1 >> v2 >> len;
		graph[v1].push_back(node(v2, len));
		graph[v2].push_back(node(v1, len));
	}
	spfa(S);
	dfs(D);
	cout << count << " " << maxTeams << endl;
	for(int i = path.size() - 1; i >= 0; i--){
		cout << path[i];
		if(i == 0){
			cout << endl; 
		}else{
			cout << " ";
		}
	}
	return 0;
}

bool spfa(int s) {
	fill(d, d + N, INF);
	fill(countInq, countInq + N, 0);
	fill(inq, inq + N, false);
	d[s] = 0;
	queue<int> q;
	q.push(s);
	countInq[s]++;
	inq[s] = true;
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		inq[u] = false;
		for(int i = 0; i < graph[u].size(); i++) {
			int v = graph[u][i].v;
			int len = graph[u][i].len;
			if(d[u] + len < d[v]) {
				d[v] = d[u] + len;
				pre[v].clear();
				pre[v].insert(u);
				if(!inq[v]) {
					q.push(v);
					inq[v] = true;
					countInq[v]++;
					if(countInq[v] > N - 1){
						return false;
					}
				}
			}else if(d[u] + len == d[v]) {
				pre[v].insert(u);
				if(!inq[v]) {
					q.push(v);
					inq[v] = true;
					countInq[v]++;
					if(countInq[v] > N - 1){
						return false;
					}
				}
			}
		}
	}
	return true;
}

void dfs(int nowVisit) {
	tempPath.push_back(nowVisit);
	if(nowVisit == S){
		count++;
		int tempTeams = 0;
		for(int i = 0; i < tempPath.size(); i++){
			tempTeams += teams[tempPath[i]];
		}
		if(tempTeams > maxTeams){
			maxTeams = tempTeams;
			path = tempPath;
		}
		tempPath.pop_back();
		return; 
	}
	for(set<int>::iterator it = pre[nowVisit].begin(); it != pre[nowVisit].end(); it++){
		dfs(*it);
	}
	tempPath.pop_back();
}

C++解题报告：