JOI春合宿 2009-day3 Ski

問題文 : スキー

解法 :
全体の平均速度について2 分探索を行う.
ある平均速度vを決めると, その平均速度でt 秒間高原を滑るとtv [m] 進むこととなる.
通った道のりの総和S と, 滑った時間の総和Tについて, S ≦ Tvを満たせば, その平均速度vで高原を滑り抜けることができることが分かる.

終点はホテルIOIだけなので、これは貼られてる辺の逆辺を貼って下から登っていけば確認できる.

コード :

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

#define MAX_N (10000)
#define MAX_C (100000)

using namespace std;

struct state {
	int from, cost, avg;
	state(int from, int cost, int avg) : from(from), cost(cost), avg(avg) {}
	state() {}
};

vector<state> G[MAX_N];

double left[MAX_N];
int st[MAX_N];
int n, m, c;

bool ok(double tavg)
{
	for (int i = 0; i < n; i++) left[i] = -99999999999;
	
	left[n - 1] = 0;
	
	for (int i = n - 1; i >= 0; i--){
		for (int j = 0; j < G[i].size(); j++){
			left[G[i][j].from] = max(left[G[i][j].from], left[i] + tavg * G[i][j].cost / G[i][j].avg - G[i][j].cost);
		}
	}
	
	for (int i = 0; i < m; i++) if (left[st[i]] >= 0) return (true);
	
	return (false);
}

int main()
{
	scanf("%d %d %d", &n, &m, &c);
	
	for (int i = 0; i < m; i++){
		scanf("%d", st + i);
		st[i]--;
	}
	
	for (int i = 0; i < c; i++){
		int from, to, cost, avg;
		scanf("%d %d %d %d", &from, &to, &cost, &avg);
		G[to - 1].push_back(state(from - 1, cost, avg));
	}
	
	double left = 0, right = 10000000;
	
	while (right - left > 1e-3){
		double center = (left + right) / 2;
		if (ok(center)) right = center;
		else left = center;
	}
	
	printf("%.f\n", round(left));
	
	return (0);
}