ARC 008C - THE☆たこ焼き祭り2012

問題

http://arc008.contest.atcoder.jp/tasks/arc008_3

解法

配る順番は無視して, 各参加者へのたこ焼きの配り方のうち, 最もかかる時間が少なくなるような配り方を考えることにします.
まず問題は, 参加者を頂点, 参加者から参加者へできる限り速くたこ焼きを投げた時の所要時間を辺の重みとする重み付きグラフとして表現することができます. このようにして考えると, 各参加者へのたこ焼きの最も時間がかからない配り方というのは, 頂点0からの最短経路に対応することがわかります. よってあらかじめDijkstra's algorithmで各頂点への最短距離を計算しておきます.
次に配る順番を考えます. これはたこ焼きが届くのに, 最も時間がかかる人から順番にたこ焼きを配っていけば良いです. 以上の配り方をシミュレートして得られた答えが解となります.

ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

struct State {
    int node;
    double cost;

    State(int node, double cost) : node(node), cost(cost) {}
    bool operator>(const State& st) const {
        return cost > st.cost;
    }
};

const int MAX_N = 1010;
const double INF = 1e40;

int x[MAX_N],
    y[MAX_N],
    t[MAX_N],   // 投げることができる速度
    r[MAX_N];   // 受け取ることができる速度

// speed[i][j]:=i番目の人からj番目の人に投げることができる最大の速度
int speed[MAX_N][MAX_N];    

double cost[MAX_N];

double calc_time(int from, int to) {
    double dist = sqrt(pow(x[from] - x[to], 2) + pow(y[from] - y[to], 2));
    return dist / (double)speed[from][to];
}

int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> t[i] >> r[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            speed[i][j] = min(t[i], r[j]);
        }
    }

    for (int v = 0; v < n; v++) {
        cost[v] = INF;
    }

    // Dijkstra's algorithm
    priority_queue<State, vector<State>, greater<State>> que;
    cost[0] = 0;
    que.push(State(0, cost[0]));

    while (!que.empty()) {
        State st = que.top(); que.pop();
        int cur_node = st.node;
        double cur_cost = st.cost;
        if (cost[cur_node] < cur_cost) continue;

        for (int next_node = 0; next_node < n; next_node++) {
            double next_cost = cur_cost + calc_time(cur_node, next_node);

            // コストが小さいなら
            if (cost[next_node] > next_cost) {
                cost[next_node] = next_cost;
                que.push(State(next_node, cost[next_node]));
            }
        }
    }

    sort(cost, cost + n, greater<double>());
    double ans = 0;
    for (int i = 0; i < n - 1; i++) {
        ans = max(ans, cost[i] + (double)i);
    }

    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

感想

たこ焼き食べたい.