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;
typedef long long ll;

const int INF = 0x3f3f3f3f;
struct Edge{
	int from, to, cap;
	int flow, cost;
	Edge(int u = 0, int v = 0, int c = 0, int f = 0, int o = 0):
		from(u), to(v), cap(c), flow(f), cost(o){}
};
struct MCMF{
	int N, ver;
	vector<Edge> edges;
	vector< vector<int> > adj;
	vector<int> d, p, a, inq;

	MCMF(int Num): N(Num + 20), ver(Num), edges(0), adj(N), d(N), p(N), a(N), inq(N) { }

	inline void addEdge(int u, int v, int ca, int co){
		if(u == v) return;
		edges.emplace_back(u, v, ca, 0, co);
		adj[u].emplace_back(edges.size() - 1);
		edges.emplace_back(v, u, 0, 0, -co);
		adj[v].emplace_back(edges.size() - 1);
	}

	inline bool SPFA(int s, int t, int& flow, long long& cost){
		fill(d.begin(), d.end(), INF);
		fill(inq.begin(), inq.end(), 0);
		d[s] = 0, inq[s] = 1, p[s] = 0, a[s] = 0x3f3f3f3f;
		queue<int> q({s});
		
		while(!q.empty()){
			int u = q.front(); q.pop();
			inq[u] = 0;
			for(int i : adj[u]) {
				Edge &e = edges[i];
				if(e.cap > e.flow && d[e.to] > d[u] + e.cost){
					d[e.to] = d[u] + e.cost;
					p[e.to] = i;
					a[e.to] = min(a[u], e.cap - e.flow);
					if(!inq[e.to]){
						q.push(e.to);
						inq[e.to] = 1;
					}
				}
			}
		}
		if(d[t] >= 0x3f3f3f3f) return false;
		flow += a[t];
		cost += 1LL * d[t] * a[t];
		for(int u = t; u != s; u = edges[p[u]].from){
			edges[p[u]].flow += a[t];
			edges[p[u] ^1].flow -= a[t];
		}
		return true;
	}
	inline int minCostMaxFlow(int s, int t, ll& cost){
		int flow = 0; cost = 0;
		while(SPFA(s, t, flow, cost)) continue;
		return flow;
	}
};

int main() {
    int n, m, p, s, t;
	scanf("%d%d%d%d%d", &n, &m, &p, &s, &t);
	MCMF mcmf(n);
	for(int i = 1; i <= m; ++i){
		static int u, v, w, c;
		scanf("%d%d%d%d", &u, &v, &w, &c);
		mcmf.addEdge(u, v, c, w);
	}
    double ans = 1e19;
    int flow = 0; ll cost = 0;
    while(mcmf.SPFA(s, t, flow, cost)) {
        ans = min(ans, (double)(cost + p) / double(flow));
    }
    printf("%.10f\n", ans);

	return 0;
}