読者です 読者をやめる 読者になる 読者になる

4bitにっき

ぽよ

JOI2009春合宿Day3 スキー(Ski)

二分探索/二分法 DP

なかなかわからず、二分探索であるというところまで他の人の解説を見てしまいました。

解法

辺_{i}を通るのにかかる時間をt_{i}とすると、
t_{i}=\frac{d_{i}}{s_{i}}
ある経路を通ったときの、最終的な平均速度をV、合計の道のりをD、合計の時間をTとすると、
V=\frac{D}{T}

最初から頂点が順序付けされているし、このVをDPなどで最小化したいですね。
しかし、\frac{D}{T}を更新していこうと思うと単純な足し算などにはならないのでDPができそうにないです。

そこでVを決めつける二分探索を考えます。
Vを決めるということは、f(V)=(\frac{D}{T} \leq Vであるか) みたいな感じの二分探索です。
\frac{D}{T} \leq V、つまりD-TV \leq 0を判定するときにDPを使います。
最初はDPができませんでしたが、Vが決まっていることによって漸化式が単純な足し算になるので最小値DPが成立します。
dp[t_{i}]=min(dp[t_{i}],dp[f_{i}]+d_{i}-t_{i}V)
(辺_{i}を使うときの漸化式)

あり得る最大の平均速度(10^5以下)をUとすると、O(N\log{U})です。


具体的に値を決めつけることで計算できるようにするというのは新鮮なテクでした。

実装

血迷って逆辺を張ったりしてます。(最初はリフト側から探索するとよさそーなどと考えていた)

using namespace std;

#define int long long

const double INF = 1e10;
const double EPS = 1e-3;

struct Edge
{
	int to, d, s;
	Edge() {}
	Edge(int _to, int _d, int _s)
	{
		to = _to; d = _d; s = _s;
	}
};

int N, M, C;
vector<Edge> edge[10001];
double dp[10001];

bool IsPossible(double v)
{
	fill((double*)dp, dp + N + 1, INF);
	dp[N] = 0;
	for (int i = N; i > 0; i--)
	{
		if (dp[i] > INF - 10) continue;
		for (int j = 0; j < edge[i].size(); j++)
		{
			double t = (double)edge[i][j].d/edge[i][j].s;
			dp[edge[i][j].to] = min(dp[edge[i][j].to], dp[i] + edge[i][j].d - t*v);
		}
	}
	return dp[0] <= 0;
}

signed main()
{
	cin >> N >> M >> C;
	for (int i = 0; i < M; i++)
	{
		int a;
		cin >> a;
		edge[a].push_back(Edge(0, 0, 1));
	}
	for (int i = 0; i < C; i++)
	{
		int f, t, d, s;
		cin >> f >> t >> d >> s;
		edge[t].push_back(Edge(f, d, s));
	}
	
	double l = 0, r = INT_MAX;
	while (r - l > EPS)
	{
		double mid = (l + r)/2;
		if (IsPossible(mid)) r = mid;
		else l = mid;
	}
	printf("%lld\n", (int)(r + 0.5));
	return 0;
}