提交记录

// Problem: P10199 [湖北省选模拟 2024] 时与风 / wind
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10199
// Memory Limit: 1 GB
// Time Limit: 1500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T>
inline void read(T &x){x=0;char ch=getchar();bool f=0;while(ch<'0'||ch>'9'){if(ch == '-')f = 1;ch = getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();if(f)x=-x;}
template <typename T,typename ...Args>
inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
inline void readn(int a[],int _){for(int i=1;i<=_;i++) read(a[i]);}
constexpr int N=5e5+2;

struct edge{int to,open,close,l,r,id;};
vector<edge> g[N];

int n,m,s;
bool vis_p[N];   //标记传送锚点
bool vis_e[N];   //标记跃迁航道
int dp[N];  //每个传送锚点的最大时间
inline void dfs(int u,int edg,int l,int r)
{
	vis_p[u]=1;
	vis_e[edg]=1;
	for(edge e:g[u])
	{
		int v=e.to;
		if(v==s) continue;  //排除回到起点的情况
		if(vis_e[e.id]) continue;
		if(l<e.open||r>e.close) continue;
		vis_e[e.id]=1;
		dfs(v,e.id,e.l,e.r);
	}
	if(dp[u]) dp[u]=min(dp[u],r);
	else dp[u]=r;
}
int main()
{
	read(n,m,s);
	int ls=0,rs=0,ed=0;  //起点开始时的l,r值
	for(int i=1;i<=m;i++)
	{
		int u,v,o,c,l,r;
		read(u,v,o,c,l,r);
		g[u].push_back(edge{v,o,c,l,r,i});
		if(u==s) ls=l,rs=s,ed=i;
	}
	dfs(s,ed,ls,rs);
	int ans=0;
	// for(int i=1;i<=n;i++) cout<<dp[i]<<' ';
	for(int i=1;i<=n;i++) if(i!=s) ans=max(ans,dp[i]);
	printf("%d",ans);
	return 0;
}
/*
对于每一个航道:
若上一个航道的[l,r]值会被这一个航道的[open,close]值完美覆盖,那么可以进行跃迁
如果不能覆盖,结束飞行
若r>下一个航道的close或者l<下一个航道的open,同样不能跃迁
*/