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>
#define MAX_P 1020
#define MAX_V 220
#define inf 1<<29
#define linf (1e16)
#define eps (1e-8)
#define Eps (1e-15)
#define mod 1000000007
#define pi acos(-1.0)
#define phi (1.0+sqrt(5.0))/2.0
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define pld(a) printf("%.10Lf\n",(ld)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define Unique(v) v.erase(unique(all(v)),v.end())
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<pii> vpi;

class edge{
  public:
    int to,d,v;
    edge(int to,int d,int v):to(to),d(d),v(v){}
};

int n,m,p;
vector<edge> e[MAX_V];
double dp[MAX_V][MAX_P];

double solve(){
  double res=0.0;
  FOR(i,0,n)FOR(j,0,p+1)dp[i][j]=-1;
  dp[0][0]=0;
  FOR(i,0,p+1){
    FOR(j,0,n){
      if(dp[j][i]==-1)continue;
      FOR(k,0,e[j].size()){
        edge E=e[j][k];
        int t=min(E.d,p-i);
        int d=t+i;
        dp[E.to][d]=max(dp[E.to][d],dp[j][i]+(double)t*E.v/E.d);
      }
    }
  }
  FOR(i,0,n)res=max(res,dp[i][p]);
  return res*2.0;
}

int main()
{
  cin>>n>>m>>p;
  FOR(i,0,m){
    int s,t,d,v;
    cin>>s>>t>>d>>v;
    s--;t--;d*=2;
    e[s].pb(edge(t,d,v));
    e[t].pb(edge(s,d,v));
  }
  pd(solve());
  return 0;
}