Expert.
Put your skills to the test.

Problem summary

Travel from vertex 1 to N in a directed graph. Each edge has length C and grants D magic after traversal. Stored magic may pay for any part of later edges; unused magic persists. Minimize the total length actually walked, or report that N is unreachable.

Constraints

1 ≤ N ≤ 2000; 1 ≤ M ≤ 5000; 1 ≤ C ≤ 30; 0 ≤ D ≤ 5000.

Worked example

Official example, transcribed with whitespace restored from the PDF.

7 8
1 2 1 0
2 4 1 0
4 6 1 0
6 7 3 5
1 3 5 2
3 5 2 3
5 7 3 0
3 4 3 1

5

Solution analysis

1. Test a proposed walking budget X by treating it as initial energy. An edge can be used when energy≥C, after which energy becomes energy−C+D. This is equivalent to distributing at most X units of actual walking along the route: initial energy is just walking credit, while gifts are obtained only after the edge.
2. Keep the largest energy attainable at each vertex. Bellman-Ford style relaxation improves it along usable edges. Reverse reachability first marks vertices from which N is reachable. Reaching N succeeds immediately. If a marked vertex can still improve in the Nth full relaxation pass, an accessible energy-gaining cycle can supply arbitrarily much energy, making any remaining route to N feasible. Ignore improvements in vertices unable to reach N.
3. Feasibility is monotone in X, so binary-search X between 0 and 30(N−1). An ordinary simple route, when one exists, can always be walked entirely within this upper bound. In the sample, the route 1→3→5→7 walks five units on its first edge and uses gifts for the rest.

Why it works

Initial walking credit and magic are interchangeable units for edge payment, but both obey the same edge-before-gift ordering, proving the feasibility reduction. Relaxation preserves the maximum attainable energy among explored walks. After N passes any further strict improvement requires a positive-gain cycle on an attainable walk; this cycle is repeatable since energy only increases on repetition. If that cycle can reach N, sufficiently many repetitions finance a simple continuation. Without such an improvement, optimal finite energies are attained on walks with all nonpositive-gain cycles removed, hence within N−1 edges. Therefore the test is exact, and monotone binary search returns the minimum budget.

Watch out. Magic granted by an edge cannot finance that same edge. A profitable cycle matters only if its vertex can eventually reach N.

An independently written complete program with standard headers.

// Key idea: Initial walking credit and magic are interchangeable units for edge payment, but both obey
// the same edge-before-gift ordering, proving the feasibility reduction. Relaxation preserves the
// maximum attainable energy among explored walks.
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct Edge{
    int from,to,cost,gift;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<Edge>edges(m);
    vector<vector<int>>reverse(n);
    for(Edge&e:edges){
        cin>>e.from>>e.to>>e.cost>>e.gift;
        --e.from;
        --e.to;
        reverse[e.to].push_back(e.from);
    }
    vector<int>reaches(n);
    queue<int>q;
    reaches[n-1]=1;
    q.push(n-1);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int u:reverse[v]){
            if(!reaches[u]){
                reaches[u]=1;
                q.push(u);
            }
        }
    }
    if(!reaches[0]){
        cout<<-1<<'\n';
        return 0;
    }
    auto feasible=[&](int budget){
        vector<long long>energy(n,-1);
        energy[0]=budget;
        if(n==1){
            return true;
        }
        for(int pass=1;pass<=n;++pass){
            bool changed=false;
            for(const Edge&e:edges){
                if(!reaches[e.to]||energy[e.from]<e.cost){
                    continue;
                }
                long long candidate=energy[e.from]-e.cost+e.gift;
                if(candidate>energy[e.to]){
                    energy[e.to]=candidate;
                    changed=true;
                    if(e.to==n-1||pass==n){
                        return true;
                    }
                }
            }
            if(!changed){
                return false;
            }
        }
        return false;
    };
    int low=0,high=30*(n-1);
    while(low<high){
        int middle=low+(high-low)/2;
        if(feasible(middle)){
            high=middle;
        }
        else{
            low=middle+1;
        }
    }
    cout<<low<<'\n';
}