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<iostream>
#include<queue>
#include<vector>
#include<iomanip>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef double D;
typedef pair<D,int> pdi;
 
struct edge{
  D d,v;
  int to;
  edge(D a=0,D b=0,int c=0):d(a),v(b),to(c){}
  bool operator<(edge a)const{
    return d/v > a.d/a.v;
  }
};
 
int main(){
  int n,m;
  D d;
 
  while(cin >> n >> m >> d){
    if(n==0)break;
 
    vector< vector<edge> > g(n); 
    rep(i,m){
      int s,t;
      D dis, num;
      cin >> s >> t >> dis >> num; s--; t--;
      g[s].push_back( edge(dis,num,t) );
      g[t].push_back( edge(dis,num,s) );
    }
 
    D res = 0;
    rep(i,n){
      D maxv = 0;
      for(edge e : g[i])maxv = max(maxv, e.v/e.d);
 
      vector<D> dis(n,1e15);
      dis[0] = 0;
      priority_queue< pdi, vector<pdi>, greater<pdi> > q;
      q.push( pdi(0,0) );
 
      while(q.size()){
	pdi p = q.top(); q.pop();
	D cost = p.first, cur = p.second;
	if(dis[cur]+1e-8 < cost)continue;
 
	for(edge e : g[cur]){
	  D cospa = e.v/e.d;
	  if(cospa > maxv+1e-8)continue;
	  D ncost = cost + (maxv-cospa)*e.d;
	  if(dis[e.to] > ncost + 1e-8){
	    dis[e.to] = ncost;
	    q.push( pdi(ncost,e.to) );
	  }
	}
      }
 
      res = max(res, maxv*d - 2*dis[i]);
    }
 
    cout << fixed << setprecision(10) << res << endl;
  }
}