#1161913 (C++23) No.654 Air E869120

• 問題: No.654 Air E869120
• ユーザー: ZeriToki
• 提出日時: 2026-04-29 16:56:53
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 13 ms / 2,000 ms
• コード長: 3,788 bytes
• コンパイル時間: 4,432 ms
• コンパイル使用メモリ: 356,432 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-04-29 16:57:06
• 合計ジャッジ時間: 8,236 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 5
other	AC * 35

ソースコード

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, s, n) for (int i = (s); i < (int)(n); i++)
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
const long long mod=998244353;
const long long mod2=469762049;
const long long mod100=1000000007;
struct maxflow{
    struct edge{int to;long long cap;int rev;};
    vector<vector<edge>>G;
    vector<int>level;
    vector<int>iter;
    int n;
    long long last_flow;
    maxflow(int N){
        n=N;
        last_flow=0;
        G.resize(N);
        level.resize(N);
        iter.resize(N);
    }
    void add_edge(int from,int to,long long cap){
        G[from].push_back((edge){to,cap,(int)G[to].size()});
        G[to].push_back((edge){from,0,(int)G[from].size()-1});
    }

    void get_edge(){
        for(int i=0;i<n;i++){
            for(int j=0;j<(int)G[i].size();j++){
                cout<<i<<" "<<G[i][j].to<<" "<<G[i][j].cap<<endl;
            }   
        }
    }

    void bfs(int s){
        level.assign(n,-1);
        queue<int>que;
        level[s]=0;
        que.push(s);
        while(!que.empty()){
            int v=que.front();
            que.pop();
            for(int i=0;i<(int)G[v].size();i++){
                edge &e=G[v][i];
                if(e.cap>0 && level[e.to]<0){
                    level[e.to]=level[v]+1;
                    que.push(e.to);
                }
            }
        }
    }
    long long dfs(int v,int t,long long f){
        if(v==t) return f;
        for(int &i=iter[v];i<(int)G[v].size();i++){
            edge &e=G[v][i];
            if(e.cap>0 && level[v]<level[e.to]){
                int d=dfs(e.to,t,min(f,e.cap));
                if(d>0){
                    e.cap-=d;
                    G[e.to][e.rev].cap+=d;
                    return d;
                }
            }
        }
        return 0;
    }
    long long flow(int s,int t){
        long long flow=0;
        for(;;){
            bfs(s);
            if(level[t]<0){
                last_flow+=flow;
                return last_flow;
            }
            iter.assign(n,0);
            long long f;
            while((f=dfs(s,t,LONG_LONG_MAX))>0){
                flow+=f;
            }
        }
    }
};

struct S{
    ll to,p,q,w;
};
bool operator<(const S &a,const S &b){
    return a.p<b.p;
}

int main(){
    ios::sync_with_stdio(false);
	cin.tie(nullptr);
    ll N,M,d;cin>>N>>M>>d;
    ll u[M+1],v[M+1],p[M+1],q[M+1],w[M+1];
    for(int i=1;i<=M;i++) cin>>u[i]>>v[i]>>p[i]>>q[i]>>w[i];
    vector<S>dat[N+1];
    for(int i=1;i<=M;i++){
        dat[u[i]].push_back((S){v[i],p[i],q[i]+d,w[i]});
    }
    dat[N].push_back((S){1,(ll)2e10,(ll)2e10,0});
    for(int i=1;i<=N;i++) sort(dat[i].begin(),dat[i].end());
    vector<int>num[N+1];
    int now=1;
    for(int i=1;i<=N;i++){
        for(int j=0;j<(int)dat[i].size();j++){
            num[i].push_back(now);
            ++now;
        }
    }
    maxflow F(M+2);
    for(int i=1;i<=N;i++){
        for(int j=0;j<(int)dat[i].size()-1;j++){
            F.add_edge(num[i][j],num[i][j+1],2e18);
        }
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<(int)dat[i].size();j++){
            int to=dat[i][j].to;
            S nex;
            nex.to=0;
            nex.p=dat[i][j].q;
            nex.q=0;
            nex.w=0;
            auto iter=lower_bound(dat[to].begin(),dat[to].end(),nex);
            int idx=distance(dat[to].begin(),iter);
            if(iter==dat[to].end()) continue;
            int nex_num=num[to][idx];
            F.add_edge(num[i][j],nex_num,dat[i][j].w);
        }
    }
    cout<<F.flow(1,M+1)<<endl;
}