Problem: Example

Input

3 2 3 1 3
1 2 2 1
2 3 1 2


Output

6.0000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define DEBUG(...)
#endif

#define size(v) v.size()

template <class U, class C> struct ssp {
  struct edge {
    int to;
    U cap;
    C cost;
  };
  const U inf = numeric_limits<U>::max(), eps = 1e-10;
  int n, s, t;
  vector<edge> es;
  vector<vector<int>> g;
  vector<C> d;
  vector<int> pe;
  ssp(int _n, int _s, int _t) : n(_n), s(_s), t(_t), g(n), d(n), pe(n) {}
  void add(int from, int to, U cap, C cost) {
    g[from].push_back(size(es)), es.push_back({to, cap, cost});
    g[to].push_back(size(es)), es.push_back({from, 0, -cost});
  }
  bool spfa() {
    static vector<bool> in(n);
    static vector<int> que;
    fill(begin(d), end(d), numeric_limits<C>::max());
    que.clear();
    d[s] = 0, in[s] = true, que.push_back(s);
    for (int bg = 0; bg < (int)size(que); ) {
      int v = que[bg++];
      in[v] = false;
      for (int id : g[v]) {
        auto&& e = es[id];
        if (e.cap > eps and d[v] + e.cost < d[e.to]) {
          d[e.to] = d[v] + e.cost, pe[e.to] = id;
          if (not in[e.to]) in[e.to] = true, que.push_back(e.to);
        }
      }
    }
    return d[t] < numeric_limits<C>::max();
  }
  vector<pair<U, C>> min_cost_max_flow() {
    U flow = 0;
    C cost = 0;
    vector<pair<U, C>> res;
    while (spfa()) {
      U df = inf;
      for (int v = t; v != s; v = es[pe[v] ^ 1].to) df = min(df, es[pe[v]].cap);
      for (int v = t; v != s; v = es[pe[v] ^ 1].to)
        es[pe[v]].cap -= df, es[pe[v] ^ 1].cap += df;
      flow += df, cost += df * d[t];
      res.emplace_back(flow, cost);
    }
    return res;
  }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int n, m, p, s, t;
  cin >> n >> m >> p >> s >> t;
  --s, --t;
  ssp<int, int> g(n, s, t);
  while (m--) {
    int v, w, d, c;
    cin >> v >> w >> d >> c;
    --v, --w;
    g.add(v, w, c, d);
  }
  double res = 1e10;
  for (auto e : g.min_cost_max_flow()) {
    double x, y;
    tie(x, y) = e;
    res = min(res, (y + p) / x);
  }
  cout << res << '\n';
}