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

本文设计知识点

C++BFS算法

P9126 [USACO23FEB] Moo Route II S

题目描述

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

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

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

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

输入格式

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

接下来的 $M$ 行描述航班信息。其中第 $j$ 行包含 $c_j,r_j,d_j,s_j$，依次表示航班的起飞机场、起飞时间、降落机场和降落时间。$(1\le c_j,d_j\le N,0\le r_j,s_j\le 10^9)$

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

输出格式

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

样例 1 的解释

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

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

样例 2 的解释

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

评分标准

• 测试点 $3-5$：对于每个 $j$，$r_j<s_j$，也就是说所有航班的到达时间晚于起飞时间。
• 测试点 $6-10$：$N,M\le 5000$
• 测试点 $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 _DEBUGfreopen("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++**实现。