結果

問題 No.654 Air E869120
ユーザー vjudge1
提出日時 2025-05-21 11:37:59
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 171 ms / 2,000 ms
コード長 1,967 bytes
コンパイル時間 2,144 ms
コンパイル使用メモリ 172,384 KB
実行使用メモリ 77,320 KB
最終ジャッジ日時 2025-05-21 11:38:06
合計ジャッジ時間 6,495 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define se second
#define fi first
const int N=1000005;
int n,m,s,t;
int w,ans,dis[N];
int tot=1,vis[N],pre[N],head[N],flag[2505][2505];
struct node{
	int to,nxt,val;
}e[N];
int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void add(int u,int v,int w){
	if(flag[u][v]==0){
		e[++tot].to=v;
		e[tot].val=w;
		e[tot].nxt=head[u];
		head[u]=tot;
		e[++tot].to=u;
		e[tot].val=0;
		e[tot].nxt=head[v];
		head[v]=tot;
		flag[u][v]=tot;
	}
	else e[flag[u][v]-1].val+=w;
}
int bfs(){
	memset(vis,0,sizeof(vis));
	queue<int>q;
	q.push(s);
	vis[s]=1;
	dis[s]=2100000000;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=e[i].nxt){
			if(e[i].val==0)continue;
			int v=e[i].to;
			if(vis[v]==1)continue;
			dis[v]=min(dis[x],e[i].val);
			pre[v]=i;
			q.push(v);
			vis[v]=1;
			if(v==t)return 1;
		}
	}
	return 0;
}
void dfs(){
	int x=t;
	while(x!=s){
		int v=pre[x];
		e[v].val-=dis[t];
		e[v^1].val+=dis[t];
		x=e[v^1].to;
	}
	ans+=dis[t];
}
struct kkk{
	int v,p,q,w;
}; 
vector<kkk>a[N];
vector<pii>tt[N];
int cnt,d;
signed main() {
//	freopen("travel.in","r",stdin);
//	freopen("travel.out","w",stdout); 
	cin>>n>>m>>d; 
	for(int i=1;i<=m;i++){
		int x=read();
		int v,p,q,w;
		cin>>v>>p>>q>>w;
		if(x!=n)a[x].push_back({v,p,q,w});
		if(x!=n){
			tt[x].push_back({cnt+1,cnt+2});
			add(cnt+1,cnt+2,w);
			cnt+=2;
		}
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<a[i].size();j++){
			if(a[i][j].v==n){
				add(tt[i][j].se,cnt+1,a[i][j].w);
				continue;
			}
			for(int k=0;k<a[a[i][j].v].size();k++){
				if(a[a[i][j].v][k].p>=a[i][j].q+d){
					add(tt[i][j].se,tt[a[i][j].v][k].fi,a[i][j].w);
				}
			}
		}
	}
	s=cnt+2;
	t=cnt+1;
	for(int j=0;j<a[1].size();j++){
		add(s,tt[1][j].fi,1e18);
	}
	while(bfs())dfs();
	cout<<ans;
	return 0;
}
0