Problem: Example

Input

3 3 4
1 2 1 1
2 3 2 4
3 1 1 1


Output

6

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 200

struct Edge{
	Edge(int arg_to,double arg_length,double arg_people,double arg_value){
		to = arg_to;
		length = arg_length;
		people = arg_people;
		value = arg_value;
	}
	int to;
	double length,people,value;
};

struct Info{
	Info(int arg_node_id,double arg_sum_cost){

		node_id = arg_node_id;
		sum_cost = arg_sum_cost;
	}
	bool operator<(const struct Info &arg) const{
		return sum_cost > arg.sum_cost;
	}
	int node_id;
	double sum_cost;
};

int V,E;
double P,min_cost[NUM];
vector<Edge> G[NUM];

int main(){

	scanf("%d %d %lf",&V,&E,&P);

	int from,to;
	double length,people;

	for(int loop = 0; loop < E; loop++){

		scanf("%d %d %lf %lf",&from,&to,&length,&people);
		from--;
		to--;
		G[from].push_back(Edge(to,length,people,people/length));
		G[to].push_back(Edge(from,length,people,people/length));
	}

	double ans = 0,base_value,base_sum;
	int start = 0;

	priority_queue<Info> Q;
	int next_node;
	double next_cost,tmp_length,tmp_people;

	for(int base_node = 0; base_node < V; base_node++){

		base_value = 0;
		for(int i = 0; i < G[base_node].size(); i++){
			base_value = max(base_value,G[base_node][i].value);
		}

		base_sum = base_value*(P/2);

		for(int i = 0; i < V; i++)min_cost[i] = (double)BIG_NUM;
		min_cost[start] = 0;

		while(!Q.empty())Q.pop();

		Q.push(Info(start,0));

		while(!Q.empty()){

			if(Q.top().node_id == base_node){
				break;
			}else if(Q.top().sum_cost > min_cost[Q.top().node_id]){
				Q.pop();
			}else{

				for(int i = 0; i < G[Q.top().node_id].size(); i++){

					if(G[Q.top().node_id][i].value >= base_value)continue;

					next_node = G[Q.top().node_id][i].to;
					tmp_length = G[Q.top().node_id][i].length;
					tmp_people = G[Q.top().node_id][i].people;
					next_cost = Q.top().sum_cost+(base_value*tmp_length-tmp_people);

					if(min_cost[next_node] > next_cost){

						min_cost[next_node] = next_cost;
						Q.push(Info(next_node,next_cost));
					}
				}
				Q.pop();
			}
		}
		ans = max(ans,base_sum-min_cost[base_node]);
	}

	printf("%.10lf\n",2*ans);

	return 0;
}