USACO23FEB-Silver C

题目来源（From）

洛谷：USACO23FEB Moo Route II S(C) - 题目

SPOJ：USACO23FEB Moo Route II S(C) - 题目

题解：USACO23FEB Moo Route II S(C) - 题解

题目（Problem）

题目描述

在度假！由于最近的一些技术进步，将通过技术先进的飞机旅行，甚至可以进行时间旅行。此外，如果两个“平行”版本的相遇，也没有问题。

全国有个机场，编号为，也有个穿越航班（）。航班在时间从机场起飞，在时间到达机场（，是可能的）。另外，她必须在机场停留时间（）。

也就是说，如果乘坐的航班在时间到达机场，那么如果，她就可以在时间换乘离开机场的航班。中途停留不影响到达机场的时间。

在时间从城市出发。对于从到的每个机场，请你计算到达每个城市的最早时间？如果不能到达，输出 -1。

输入格式

第一行输入两个整数和。

接下来的行。每行四个整数，描述第个航班的信息。

接下来一行，包含个整数：，分别表示在每个机场停留的时间。

输出格式

输出行，每行一个整数，第行表示能到达机场的最早时间。如果贝西不可能到达机场，则输出 -1。

样例

输入数据 1

输出数据 1

0
0
20

样例1说明

可以乘坐列出的顺序中的个航班，这使她能够在时间到达机场和，在时间到达机场。

请注意，这条路线经过号机场两次，首先从时间开始，然后从时间开始。

输入数据 2

输出数据 2

0
10
-1

样例2说明

在这种情况下，可以乘坐号航班，在时间到达号机场。然而，由于起飞时间是点，她不能进行个时间单位的停留，所以她没有及时到达，也不能乘坐号航班。

数据规模与约定

测试点：；对于所有，所有航班起飞后到达。
测试点：
测试点：没有其它约定。

题解（Solution）

直接抄的题解：

一个重要的性质：每个航班是不会被重复乘坐的。因为，不管你在什么前提下乘坐了某个航班，这个航班对你造成的影响是完全相同的。

这让的实现成为可能。

从点开始。枚举所有离港航班，若该航班未被乘坐且时间合法，则乘坐，并更新航班终点的答案；否则不乘坐。

这样做是的，考虑剪枝。

将一个机场出发的航班按降序排序。枚举出发航班时，如果当前枚举到的航班已经出发的太早了，就掉。

依旧是。

因为，我们会多次访问一个机场，每次都要枚举它的大多数出边（其中绝大多数枚举都是重复的）。考虑存储代表点上一次枚举到了哪里，下次从这里开始枚举。这样每条边只会经过次枚举。时间复杂度(或者说)。

代码（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;
}