JOI2009春合宿Day3 スキー(Ski)
なかなかわからず、二分探索であるというところまで他の人の解説を見てしまいました。
解法
を通るのにかかる時間をとすると、
ある経路を通ったときの、最終的な平均速度を、合計の道のりを、合計の時間をとすると、
最初から頂点が順序付けされているし、このをDPなどで最小化したいですね。
しかし、を更新していこうと思うと単純な足し算などにはならないのでDPができそうにないです。
そこでを決めつける二分探索を考えます。
を決めるということは、 みたいな感じの二分探索です。
、つまりを判定するときにDPを使います。
最初はDPができませんでしたが、Vが決まっていることによって漸化式が単純な足し算になるので最小値DPが成立します。
()
あり得る最大の平均速度(10^5以下)を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; }