提出 #494426

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

#define for_(i,a,b) for(int i=(a);i<(b);++i)

struct Edge {
	int to, d, v;
};

vector< Edge > edges[222];
double dp[1010][222];

void maxUpdate(double& a, double b) { a = max(a, b); }

int main() {
	int N, M, P;
	cin >> N >> M >> P;
	
	for_(i,0,M) {
		int s, t, d, v;
		cin >> s >> t >> d >> v;
		--s; --t;
		edges[s].push_back(Edge{t, d, v});
		edges[t].push_back(Edge{s, d, v});
	}
	
	for_(i,0,1010) for_(j,0,222) dp[i][j] = -1.0;//0.0;
	dp[0][0] = 0.0;
	
	for_(p,0,P) {
		int pp = P - 2 * p;
		if (pp < 0) break;
		
		for_(v,0,N) {
			if (dp[p][v] < 0) continue;
			
			for (Edge e : edges[v]) {
				if (p + e.d <= P) maxUpdate(dp[p + e.d][e.to], dp[p][v] + (double)e.v);
				maxUpdate(dp[P][0], 2. * dp[p][v] + (double)pp * (double)e.v / (double)e.d);
			}
		}
	}
	
	printf("%.9lf", dp[P][0]);
}

提出情報

ジャッジ結果