COGS 1825 [USACO Jan11]道路与航线

由于 $T \leq 25000,R+P \leq 100000$ ，优先考虑SPFA，

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
	memset(d, 0x3f, sizeof(d));
	memset(vis, 0, sizeof(vis));
	memset(p, 0, sizeof(p));
	queue<int> q;
	q.push(s);
	vis[s] = true;
	d[s] = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		vis[x] = 0;
		for (int i = 0; i < v[x].size(); i++) {
			if (d[v[x][i].first] > d[x] + v[x][i].second) {
				d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
				if (!vis[v[x][i].first]) q.push(v[x][i].first), vis[v[x][i].first] = true;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> R >> P >> S;
	for (int i = 1; i <= R; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= P; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
	}
	SPFA(S);
	for (int i = 1; i <= T; i++) {
		if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
		else cout << d[i] << endl;
	}
	return 0;
}

最终评测T两个点，考虑换方法。

查看资料注意到SPFA有双端队列优化和优先队列优化，优先队列复杂度 $O(logn)$，故不考虑。双端队列优化思路是：将要加入的节点与队头比较，小于等于插到队头，大于则插到队尾，时间复杂度接近 $O(1)$。

重写代码

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > v[25005];
int d[25005];
bool vis[25005];
int p[25005];
int T, R, P, S;
void SPFA(int s) {
	memset(d, 0x3f, sizeof(d));
	memset(vis, 0, sizeof(vis));
	memset(p, 0, sizeof(p));
	deque<int> q;
	q.push_back(s);
	vis[s] = true;
	d[s] = 0;
	while (!q.empty()) {
		int x = q.front();
		q.pop_front();
		vis[x] = 0;
		for (int i = 0; i < v[x].size(); i++) {
			if (d[v[x][i].first] > d[x] + v[x][i].second) {
				d[v[x][i].first] = d[x] + v[x][i].second, p[v[x][i].first] = x;
				//主要改动如下
				if (!vis[v[x][i].first]) {
					if (d[v[x][i].first] <= d[q.front()]) q.push_front(v[x][i].first);
					else q.push_back(v[x][i].first);
					vis[v[x][i].first] = true;
				}
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T >> R >> P >> S;
	for (int i = 1; i <= R; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
		v[b].push_back(make_pair(a, c));
	}
	for (int i = 1; i <= P; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back(make_pair(b, c));
	}
	SPFA(S);
	for (int i = 1; i <= T; i++) {
		if (d[i] == 0x3f3f3f3f) cout << "NO PATH" << endl;
		else cout << d[i] << endl;
	}
	return 0;
}

后记

在知乎上看到文章关于SPFA的各种优化以及对应hack，可以参考（如何看待 SPFA 算法已死这种说法？ - 知乎 (zhihu.com)）。