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;
struct Edge{
  double v;
  int d;
};
int main(){
  int n,m,p;
  int i,j,k;
  cin >> n >> m >> p;
  Edge edge[n+1][n+1];
  for(i=0;i<=n;i++){
    for(j=0;j<=n;j++){
      edge[i][j].d=0;
      edge[i][j].v=0;
    }
  }
  for(i=0;i<m;i++){
    cin >> j >> k ;
    cin >> edge[j][k].d >> edge[j][k].v;
    edge[k][j].d=edge[j][k].d;
    edge[k][j].v=edge[j][k].v;
  }
  
  //cout << n << m << p << endl;
  
  double dp[201][2005]={{}};
  //memset(dp,-1,sizeof(dp));
  for(i=0;i<201;i++){
    for(j=0;j<2005;j++){
      dp[i][j]=-1;
    }
  }
  dp[1][0]=0;
  for(i=0;i<p;i++){
    for(j=1;j<=n;j++){
      if(dp[j][i]==-1) continue;
      for(k=1;k<=n;k++){
	if(edge[j][k].d==0) continue;
	dp[j][i+1]=max(dp[j][i+1],dp[j][i]+(edge[j][k].v/edge[j][k].d));
	//cout << i << ":" << j << ":" << k <<"/"<< edge[j][k].d << endl;
	dp[k][i+edge[j][k].d]=max(dp[k][i+edge[j][k].d],dp[j][i]+edge[j][k].v);
      }
    }
  }
  //cout << dp[1][p] << endl;
  printf("%.6lf\n",dp[1][p]);
}