48分WA求调闭关

#include <bits/stdc++.h>
using namespace std;
const long long max_inf = 1e18;
struct E {
    int t, r;
    long long c;
    E(int tt, int rr, long long cc) : t(tt), r(rr), c(cc) {}
};
vector<pair<int, long long>> rg[305];
vector<E> g[305];
vector<tuple<int, int, long long, long long>> e;
long long d[305];
int mvp[305], cy[305];
int n, m;
long long c;
void f1(int s) 
{
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    for (int i = 1; i <= n; i++) d[i] = max_inf;
    d[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) 
	{
        auto [dis, u] = pq.top();
        pq.pop();
        if (dis > d[u]) continue;
        for (auto [v, w] : rg[u]) 
		{
            if (d[v] > d[u] + w) 
			{
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
}
void add(int u, int v, long long cc) 
{
    g[u].emplace_back(v, g[v].size(), cc);
    g[v].emplace_back(u, g[u].size()-1, 0);
}
bool bfs(int s, int t) 
{
    memset(mvp, -1, sizeof(mvp));
    queue<int> q;
    mvp[s] = 0;
    q.push(s);
    while (!q.empty()) 
	{
        int u = q.front();
        q.pop();
        for (auto &ed : g[u]) 
		{
            if (ed.c > 0 && mvp[ed.t] == -1) 
			{
                mvp[ed.t] = mvp[u] + 1;
                q.push(ed.t);
                if (ed.t == t) return true;
            }
        }
    }
    return false;
}
long long dfs(int u, int t, long long f) 
{
    if (u == t) return f;
    for (int &i = cy[u]; i < g[u].size(); i++) 
	{
        E &ed = g[u][i];
        if (ed.c > 0 && mvp[ed.t] == mvp[u] + 1) 
		{
            long long ff = dfs(ed.t, t, min(f, ed.c));
            if (ff > 0) 
			{
                ed.c -= ff;
                g[ed.t][ed.r].c += ff;
                return ff;
            }
        }
    }
    return 0;
}
long long f2(int s, int t) 
{
    long long res = 0;
    while (bfs(s, t)) 
	{
        memset(cy, 0, sizeof(cy));
        while (long long ff = dfs(s, t, max_inf))
		{
            res += ff;
            if (res >= c) break;
        }
        if (res >= c) break;
    }
    return res;
}
int main() 
{
    //freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> c;
    for (int i = 0; i < m; i++) 
	{
        int u, v;
        long long l, t;
        cin >> u >> v >> l >> t;
        e.emplace_back(u, v, l, t);
        rg[v].emplace_back(u, t);
    }
    f1(n);
    if (d[1] == max_inf) 
	{
        cout << -1 << endl;
        return 0;
    }
    long long L = 0, R = max_inf, ans = max_inf;
    while (L <= R) 
	{
        long long mid = L + (R - L) / 2;
        for (int i = 1; i <= n; i++) g[i].clear();
        for (auto [u, v, l, t] : e) 
		{
            long long sum = mid - t - d[v];
            long long w = 0;
            if (sum >= 0) 
			{
                if (l > c / (sum + 1)) w = c;
                else w = l * (sum + 1);
            }
            add(u, v, w);
        }
        long long f = f2(1, n);
        if (f >= c) 
		{
            ans = mid;
            R = mid - 1;
        } 
		else L = mid + 1;
    }
    cout << ans << endl;
    return 0;
}