USACO23FEB-Silver C
题目来源（From）
洛谷：USACO23FEB Moo Route II S(C) - 题目
SPOJ：USACO23FEB Moo Route II S(C) - 题目
题解：USACO23FEB Moo Route II S(C) - 题解
题目（Problem）
题目描述
$Bessie$ 在度假！由于最近的一些技术进步，$Bessie$ 将通过技术先进的飞机旅行，甚至可以进行时间旅行。此外，如果两个“平行”版本的 $Bessie$ 相遇，也没有问题。
全国有 $N$ 个机场，编号为 $1,2,…,N$ ，也有 $M$ 个穿越航班（$1≤N,M≤200000$）。$j$ 航班在 $r_j$ 时间从 $c_j$ 机场起飞，在 $s_j$ 时间到达 $d_j$ 机场（$0≤r_j,s_j≤10^9$ ，$s_j<r_j$ 是可能的）。另外，她必须在 $i$ 机场停留 $a_i$ 时间（$1\le a_i\le10^9$）。
也就是说，如果 $Bessie$ 乘坐的航班在时间 $s$ 到达机场 $i$，那么如果 $r\ge s+a_i$，她就可以在时间 $r$ 换乘离开机场的航班。中途停留不影响 $Bessie$ 到达机场的时间。
$Bessie$ 在时间 $0$ 从城市 $1$ 出发。对于从 $1$ 到 $N$ 的每个机场，请你计算 $Bessie$ 到达每个城市的最早时间？如果不能到达，输出 -1。
输入格式
第一行输入两个整数 $N$ 和 $M$。
接下来的 $M$ 行。每行四个整数 $c_j,r_j,d_j,s_j (1\le c_j,d_j\le N ; 0\le r_j,s_j\le 109)$ ，描述第 $j$ 个航班的信息。
接下来一行，包含 $N$ 个整数：$a_1,a_2,\dots ,a_N$，分别表示在每个机场停留的时间。
输出格式
输出 $N$ 行，每行一个整数，第 $i$ 行表示 $Bessie$ 能到达机场 $i$ 的最早时间。如果贝西不可能到达机场，则输出 -1。
样例
输入数据 1
3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10输出数据 1
0
0
20样例1说明
$Bessie$ 可以乘坐列出的顺序中的 $3$ 个航班，这使她能够在时间 $0$ 到达机场 $1$ 和 $2$ ，在时间 $20$ 到达机场 $3$。
请注意，这条路线经过 $2$ 号机场两次，首先从时间 $10−11$ 开始，然后从时间 $0−1$ 开始。
输入数据 2
3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10输出数据 2
0
10
-1样例2说明
在这种情况下，$Bessie$ 可以乘坐 $1$ 号航班，在时间 $10$ 到达 $2$ 号机场。然而，由于起飞时间是 $10$ 点，她不能进行 $1$ 个时间单位的停留，所以她没有及时到达，也不能乘坐 $2$ 号航班。
数据规模与约定
- 测试点 $3-5$ ：$r_j<s_j$；对于所有 $j$，所有航班起飞后到达。
- 测试点 $6-10$ ：$1\le N,M\le 5000$
- 测试点 $11-20$ ：没有其它约定。
题解（Solution）
直接抄的题解：
一个重要的性质：每个航班是不会被重复乘坐的。因为，不管你在什么前提下乘坐了某个航班，这个航班对你造成的影响是完全相同的。
这让 $O(M)$ 的 $dfs$ 实现成为可能。
从 $1$ 点开始 $dfs$ 。枚举所有离港航班，若该航班未被乘坐且时间合法，则乘坐，并更新航班终点的答案；否则不乘坐。
这样做是 $O(NM)$ 的，考虑剪枝。
将一个机场出发的航班按 $r$ 降序排序。枚举出发航班时，如果当前枚举到的航班已经出发的太早了，就 $break$ 掉。
依旧是 $O(NM)$ 。
因为，我们会多次访问一个机场，每次都要枚举它的大多数出边（其中绝大多数枚举都是重复的）。考虑存储 $ind_i$ 代表 $i$ 点上一次枚举到了哪里，下次从这里开始枚举。这样每条边只会经过 $1$ 次枚举。时间复杂度 $O(M)$ (或者说 $O(N+M)$ )。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long
inline int input(){char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;}
const int inf = 0x3f3f3f3f3f3f3f;
const int N = 1012345;
int n,m,a[N];
struct T{int y,st,ed;};
vector<T> ft[N];
int d[N],fir[N];
bitset<N> vst;
void Spfa(int st){
d[st]=-a[1];vst[st]=true;
queue<int> q;q.push(st);
while(q.size()){
int x=q.front();q.pop();
vst[x]=false;
Rof(i,fir[x],0){
T e=ft[x][i];if(e.st < d[x]+a[x]) break;//如果已经超过起飞时间
int y=e.y;
if(d[y]>e.ed){
d[y]=e.ed;
if(vst[y]==0) q.push(y),vst[y]=true;
}fir[x]=i-1;
}
}
}
inline bool cmp(T a,T b){return a.st==b.st?a.ed<b.ed:a.st<b.st;}
signed main(){
string str("c");
freopen((str+".in").c_str(),"r",stdin);
freopen((str+".out").c_str(),"w",stdout);
memset(d,0x3f,sizeof(d));vst.reset();
cin>>n>>m;
For(i,1,m){
int x=input(),st=input(),y=input(),ed=input();
ft[x].push_back({y,st,ed});
}For(x,1,n){
cin>>a[x];
sort(ft[x].begin(),ft[x].end(),cmp);
fir[x]=ft[x].size()-1;
}Spfa(1);printf("0\n");
For(x,2,n) cout<<(d[x]>=inf?-1ll:d[x])<<'\n';
return 0;
}
