【BFS】P9126 [USACO23FEB] Moo Route II S|普及+

发布于：2025-06-24 ⋅ 阅读:(17) ⋅ 点赞:(0)

本文设计知识点

C++BFS算法

P9126 [USACO23FEB] Moo Route II S

题目描述

注意：本题的时间限制为 4 秒，是默认限制的两倍。

Bessie 正在度假！由于最近的技术进步，Bessie 可以通过先进的航班旅行，这些航班甚至可以进行时间旅行。此外，即使存在多个“平行”的 Bessie 同时出现也不会有任何问题。

在这个国家，有 N N N 个机场，编号为 1 , 2 , ⋯   , N 1,2,\cdots,N 1,2,⋯,N，以及 M M M 条时间旅行航班（ 1 ≤ N , M ≤ 200000 1 \leq N,M \leq 200000 1≤N,M≤200000）。第 j j j 条航班从机场 c j c_j cj​ 在时间 r j r_j rj​ 起飞，并在时间 s j s_j sj​ 抵达机场 d j d_j dj​（ 0 ≤ r j , s j ≤ 10 9 0 \leq r_j,s_j \leq 10^9 0≤rj​,sj​≤109， s j < r j s_j < r_j sj​<rj​ 是可能的）。此外，Bessie 在机场 i i i 需要停留 a i a_i ai​ 时间（ 1 ≤ a i ≤ 10 9 1 \leq a_i \leq 10^9 1≤ai​≤109）。也就是说，如果 Bessie 乘坐一趟航班在时间 s s s 抵达机场 i i i，她可以转乘一趟从该机场出发的航班，只要该航班的起飞时间 r ≥ s + a i r \geq s + a_i r≥s+ai​。需要注意的是，停留时间不会影响 Bessie 抵达某机场的实际时间。

Bessie 从城市 1 1 1 出发，起始时间为 0 0 0。对于从 1 1 1 到 N N N 的每个机场，求出 Bessie 最早可以到达该机场的时间。

输入格式

第一行输入包含两个整数 N N N 和 M M M。

接下来的 M M M 行描述航班信息。其中第 j j j 行包含 c j , r j , d j , s j c_j, r_j, d_j, s_j cj​,rj​,dj​,sj​，依次表示航班的起飞机场、起飞时间、降落机场和降落时间。 ( 1 ≤ c j , d j ≤ N , 0 ≤ r j , s j ≤ 10 9 ) (1 \leq c_j,d_j \leq N, 0 \leq r_j,s_j \leq 10^9) (1≤cj​,dj​≤N,0≤rj​,sj​≤109)

接下来的 1 1 1 行描述每个机场的停留时间。该行包含 N N N 个用空格分隔的整数，分别为 a 1 , ⋯   , a N a_1,\cdots,a_N a1​,⋯,aN​。

输出格式

输出共 N N N 行。第 i i i 行输出 Bessie 最早到达机场 i i i 的时间；如果无法到达该机场，输出 − 1 -1 −1。

样例 1 的解释

Bessie 可以按照给定的顺序乘坐第 3 3 3 班航班，这使她可以在时间 0 0 0 到达机场 1 1 1 和机场 2 2 2，以及在时间 20 20 20 到达机场 3 3 3。

注意，这条路线会两次经过机场 2 2 2，第一次是在时间 10 − 11 10-11 10−11，第二次是在时间 0 − 1 0-1 0−1。

样例 2 的解释

在这个例子中，Bessie 可以乘坐第 1 1 1 班航班，在时间 10 10 10 抵达机场 2 2 2。但是，她无法及时赶上第 2 2 2 班航班，因为该航班的起飞时间为 10 10 10，而她需要至少 1 1 1 个时间单位来完成停留。

评分标准

  • 测试点 3 − 5 3-5 3−5：对于每个 j j j， r j < s j r_j < s_j rj​<sj​，也就是说所有航班的到达时间晚于起飞时间。
  • 测试点 6 − 10 6-10 6−10： N , M ≤ 5000 N,M \leq 5000 N,M≤5000
  • 测试点 11 − 20 11-20 11−20：无额外限制。

输入输出样例 #1

输入 #1

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10

输出 #1

0
0
20

输入输出样例 #2

输入 #2

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10

输出 #2

0
10
-1

BFS

普通BFS：一个点只处理一次；本题：一条边只处理一次。同一条航班到达时间一致，故后序航班不会发生变化。
neiBo[i] 记录所有 { btime,etime,j }
航班起点i，终点j，出发时间btime,到达时间etime。neiBo[i] 升序。
dis[i] 记录到达城市i的最短时间。队列记录{到达时间，到达城市
}。
通过{time, cur}处理队中元素
如果time < dis[cur]，则更新dis[cur]。
如果get < 0 > (neiBo[cur].back()) >= time + a[cur] { get < 1 >,get < 2 >}
入队，neiBo[cur] 出栈
** 时间复杂度**：O(NM)
# 代码
## 核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>
#include<array>

#include <bitset>
using namespace std;

template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {
	in >> pr.first >> pr.second;
	return in;
}

template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t);
	return in;
}

template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {
	in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
	return in;
}

template<class T = int>
vector<T> Read() {
	int n;
	cin >> n;
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}
template<class T = int>
vector<T> ReadNotNum() {
	vector<T> ret;
	T tmp;
	while (cin >> tmp) {
		ret.emplace_back(tmp);
		if ('\n' == cin.get()) { break; }
	}
	return ret;
}

template<class T = int>
vector<T> Read(int n) {
	vector<T> ret(n);
	for (int i = 0; i < n; i++) {
		cin >> ret[i];
	}
	return ret;
}

template<int N = 1'000'000>
class COutBuff
{
public:
	COutBuff() {
		m_p = puffer;
	}
	template<class T>
	void write(T x) {
		int num[28], sp = 0;
		if (x < 0)
			*m_p++ = '-', x = -x;

		if (!x)
			*m_p++ = 48;

		while (x)
			num[++sp] = x % 10, x /= 10;

		while (sp)
			*m_p++ = num[sp--] + 48;
		AuotToFile();
	}
	void writestr(const char* sz) {
		strcpy(m_p, sz);
		m_p += strlen(sz);
		AuotToFile();
	}
	inline void write(char ch)
	{
		*m_p++ = ch;
		AuotToFile();
	}
	inline void ToFile() {
		fwrite(puffer, 1, m_p - puffer, stdout);
		m_p = puffer;
	}
	~COutBuff() {
		ToFile();
	}
private:
	inline void AuotToFile() {
		if (m_p - puffer > N - 100) {
			ToFile();
		}
	}
	char  puffer[N], * m_p;
};

template<int N = 1'000'000>
class CInBuff
{
public:
	inline CInBuff() {}
	inline CInBuff<N>& operator>>(char& ch) {
		FileToBuf();
		while (('\r' == *S) || ('\n' == *S) || (' ' == *S)) { S++; }//忽略空格和回车
		ch = *S++;
		return *this;
	}
	inline CInBuff<N>& operator>>(int& val) {
		FileToBuf();
		int x(0), f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行		
		return *this;
	}
	inline CInBuff& operator>>(long long& val) {
		FileToBuf();
		long long x(0); int f(0);
		while (!isdigit(*S))
			f |= (*S++ == '-');
		while (isdigit(*S))
			x = (x << 1) + (x << 3) + (*S++ ^ 48);
		val = f ? -x : x; S++;//忽略空格换行
		return *this;
	}
	template<class T1, class T2>
	inline CInBuff& operator>>(pair<T1, T2>& val) {
		*this >> val.first >> val.second;
		return *this;
	}
	template<class T1, class T2, class T3>
	inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val);
		return *this;
	}
	template<class T1, class T2, class T3, class T4>
	inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {
		*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
		return *this;
	}
	template<class T = int>
	inline CInBuff& operator>>(vector<T>& val) {
		int n;
		*this >> n;
		val.resize(n);
		for (int i = 0; i < n; i++) {
			*this >> val[i];
		}
		return *this;
	}
	template<class T = int>
	vector<T> Read(int n) {
		vector<T> ret(n);
		for (int i = 0; i < n; i++) {
			*this >> ret[i];
		}
		return ret;
	}
	template<class T = int>
	vector<T> Read() {
		vector<T> ret;
		*this >> ret;
		return ret;
	}
private:
	inline void FileToBuf() {
		const int canRead = m_iWritePos - (S - buffer);
		if (canRead >= 100) { return; }
		if (m_bFinish) { return; }
		for (int i = 0; i < canRead; i++)
		{
			buffer[i] = S[i];//memcpy出错			
		}
		m_iWritePos = canRead;
		buffer[m_iWritePos] = 0;
		S = buffer;
		int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
		if (readCnt <= 0) { m_bFinish = true; return; }
		m_iWritePos += readCnt;
		buffer[m_iWritePos] = 0;
		S = buffer;
	}
	int m_iWritePos = 0; bool m_bFinish = false;
	char buffer[N + 10], * S = buffer;
};

class Solution {
public:
	vector<int> Ans(const int N, vector<tuple<int, int, int, int>>& edge, const vector<int>& a) {
		for (auto& [s, t1, d, t2] : edge) {
			s--; d--;
		}
		vector < vector<tuple<int, int, int>>> neiBo(N);
		for (const auto& [s, t1, d, t2] : edge) {
			neiBo[s].emplace_back(t1, d, t2);
		}
		for (auto& v : neiBo) {
			sort(v.begin(), v.end());
		}
		vector<int> ans(N, INT_MAX / 2);
		queue<pair<int, int>> que;
		auto Add = [&](int cur, int time) {
			que.emplace(cur, time);
			ans[cur] = min(ans[cur], time);
		};
		Add(0, -a[0]);
		while (que.size()) {
			const auto [cur, time] = que.front(); que.pop();
			auto& v = neiBo[cur];
			while (v.size() && (get<0>(v.back()) >= time + a[cur])) {
				Add(get<1>(v.back()), get<2>(v.back()));
				neiBo[cur].pop_back();
			}
		}
		for (auto& i : ans) {
			if (INT_MAX / 2 == i) { i = -1; }
		}
		ans[0] = 0;
		return ans;
	};
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG	
	ios::sync_with_stdio(0); cin.tie(nullptr);
	CInBuff<> in; COutBuff<10'000'000> ob;
	int N;
	in >> N ;
	auto edge = in.Read<tuple<int,int,int,int>>();	
	auto a = in.Read<int>(N);
#ifdef _DEBUG		
	printf("N=%d", N);
	Out(edge, ",edge=");
	Out(a, ",a=");
	//Out(B, "B=");
	//Out(que, "que=");
	//Out(B, "B=");
#endif // DEBUG	
	auto res = Solution().Ans(N,edge,a);
	for (const auto& i : res)
	{
		cout << i << "\n";
	}

	return 0;
}

单元测试

int N;
		vector<tuple<int, int, int, int>> edge;
		vector<int> a;
		TEST_METHOD(TestMethod1)
		{
			N = 3, edge = { {1,0,2,10},{2,11,2,0},{2,1,3,20} }, a = { 10,1,10 };
			auto res = Solution().Ans(N,edge,a);
			AssertEx({ 0,0,20 }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			N = 3, edge = { {1,0,2,10},{2,10,2,0},{2,1,3,20} }, a = { 10,1,10 };
			auto res = Solution().Ans(N, edge,a);
			AssertEx({ 0,10,-1 }, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布