第8回日本情報オリンピック 春合宿 JOI2009 3日目 問題2 「スキー」 (Ski)

二分探索の練習

平均最小化

小数の闇に注意

割と平均最大（小）化好きかもしれない。

#include <bits/stdc++.h>
using namespace std;
struct edge{
	int from;
	double time;
	int ren;
};
const int INF = 1000000000;

int n,m,c;
double dp[10009];
bool flag[10006];
vector<edge> g[10004];

bool ch(double x){
	for(int i = 1;i <= n;i++){
		if(flag[i] == true)dp[i] = 0;
		else dp[i] = -INF;
	}
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < g[i].size();j++){
			edge es = g[i][j];
			dp[i] = max(dp[i],dp[es.from]+es.time*x-es.ren);
		}
	}
	if(dp[n] >= 0)return true;
	else return false;
}

int main(){
	scanf("%d%d%d",&n,&m,&c);
	for(int i = 0;i < m;i++){
		int y;
		scanf("%d",&y);
		flag[y] = true;
	}
	for(int i = 0;i < c;i++){
		int f,t,j,s;
		scanf("%d%d%d%d",&f,&t,&j,&s);
		double tt = (double) j / (double) s;
		edge tmp = {f,tt,j};
		g[t].push_back(tmp);
	}
	double lb = 0,ub = 100000;
	while(ub - lb > 0.0001){
		double mid = (lb + ub)/2;
		if(ch(mid))ub = mid;
		else lb = mid;
	}
	printf("%.f\n",ub);
	return 0;
}