Algoogle

Algorithm for Programming Contest

JOI 春合宿 2009 Ski

Category: JOI Tag: binary-search, dp

Ski

問題概要


各地点に高さの降順に番号がふられている.
またリフトで行ける地点が指定されている.
地点同士を結ぶコースがあり, それぞれ距離と速さが決まっている.
ある場所から一番下の地点まで平均速度が一番小さいものを求め, その速度を答えよ.

解法


平均の最小化.
ある地点から一番下までいく複数のコースからなるルートRについて,
平均速度x以下で行けるかどうかは以下で判断できる

全ルートの最小値はDPで求めることができる.
dp[i] := 地点iまでの上の式の最小
リフトで行ける地点は最大で0, 他は初期値を適当に大きな数をとる.
あとは辺が上から下にしか伸びていないのと, 番号が高い方から振られていることからfor文を回してminを取るだけで更新できる.

コード


(Ski.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
const double inf = 1e9;

struct edge
{
        int to, d, s;
};

int n, m, c, a[10010];
double dp[10010];
vector<edge> G[10010];

inline void chmin(double &a, double b){a=min(a,b);}

bool ok(double x)
{
        fill(dp,dp+n,inf);
        for (int i = 0; i < m; i++) dp[a[i]] = 0;
        for (int i = 0; i < n-1; i++)
                for(auto &e: G[i])
                        chmin(dp[e.to],dp[i]+e.d-x*e.d/e.s);
        return dp[n-1] <= 0;
}

int solve()
{
        double lb = 0, ub = inf, mid;
        for (int _ = 0; _ < 100; _++) {
                mid = (lb+ub)/2;
                if(ok(mid)) ub = mid;
                else lb = mid;
        }
        return ub+0.5;
}

void input()
{
        cin >> n >> m >> c;
        for (int i = 0; i < m; i++) {
                cin >> a[i];
                a[i]--;
        }
        int f, t, d, s;
        for (int i = 0; i < c; i++) {
                cin >> f >> t >> d >> s;
                f--; t--;
                G[f].push_back((edge){t,d,s});
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments