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>
using namespace std;
#define MAX_N 205
#define MAX_P 1005
struct edge{ int to,cost,v; };

int N,M,P;

double dp[MAX_P][MAX_N];
vector<edge> G[MAX_N];

int main(){

  cin>>N>>M>>P;
  for(int i=0;i<M;i++){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    a--,b--;
    G[a].push_back((edge){b,c,d});
    G[b].push_back((edge){a,c,d});
  }
  for(int i=0;i<MAX_P;i++)
    for(int j=0;j<MAX_N;j++)
      dp[i][j]=-1e9;

  dp[0][0]=0;
  for(int i=0;i<P;i++){
    for(int j=0;j<N;j++){
      if(dp[i][j]==-1e9)continue;
      for(int k=0;k<(int)G[j].size();k++){
        edge e=G[j][k];
        dp[i+1][j]=max(dp[i+1][j],dp[i][j]+(double)e.v/(double)e.cost);
        if(i+e.cost<=P)
          dp[i+e.cost][e.to]=max(dp[i+e.cost][e.to],dp[i][j]+e.v);
      }
    }
  }

  printf("%.10f\n",dp[P][0]);
  return 0;
}