提出 #494554

---

ソースコード 拡げる

#include<iostream>
#include<vector>
#include<algorithm>
#include<sstream>
#include<set>
#include<map>
#include<string>
#include<cmath>
#include<stack>
#include<complex>
#include<queue>
#include<cassert>

using namespace std;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define irep(i, n) for(int i=n-1;i>=0;i--)
#define reep(i, s, n) for(int i=s;i<(int)n;i++)
#define ireep(i, n, s) for(int i=n-1;i>=s;i--)

#define REP(i, n) for(int i=0;i<(int)n;i++)
#define RREP(i, n) for(int i=n-1;i>=0;i--)
#define REPS(i, n) for(int i=1;i<=(int)n;i++)
#define RREPS(i, n) for(int i=n;i>0;i--)

#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define fc first
#define sc second
#define vc vector;
typedef long long ll;
typedef complex<double> Point;
typedef vector<int> vi;
typedef pair<int, int> pii;
const int IINF = 1 << 28;
const double INF = 1e20;
const double EPS = 1e-10;
const double PI = acos(-1.0);

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

int n, m, p;

signed main(){
	cin >> n >> m >> p;
	vector<vector<tuple<int, int, int>>> g(n);
	REP(i, m){
		int u, v, d, w;
		cin >> u >> v >> d >> w; u--; v--;
		g[u].eb(v, d, w);
		g[v].eb(u, d, w);		
	}
	vector<vector<int>> dp(p/2 + 1, vector<int>(n, -IINF));
	dp[0][0] = 0;
	double ans = 0;
	REP(i, p/2 + 1)REP(u, n)if(dp[i][u] > -1){
		for(auto &e : g[u]){
			int v, d, w;
			tie(v, d, w) = e;
			ans = max(ans, dp[i][u] * 2 + (double)(p - i*2) * w / d);
			if(i+d <= p/2) dp[i+d][v] = max(dp[i+d][v], dp[i][u] + w);
		}
	} 
	printf("%.20f\n", ans);
	return 0;
}

提出情報

ジャッジ結果