#1149434 (C++23) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: yimiya（いみや）
• 提出日時: 2026-02-25 23:59:00
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 6 ms / 1,000 ms
• コード長: 6,073 bytes
• コンパイル時間: 3,950 ms
• コンパイル使用メモリ: 361,196 KB
• 実行使用メモリ: 7,848 KB
• スコア: 26,752,795
• 最終ジャッジ日時: 2026-02-26 00:00:47
• 合計ジャッジ時間: 9,118 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

ファイルパターン	結果
other	AC * 100

ソースコード

#include <bits/stdc++.h>
using namespace std;

const int TIME_START = 360;  // 06:00
const int TIME_END   = 1260; // 21:00

struct City { int x, y, w; };

string fmt(int t) {
    char buf[16];
    snprintf(buf, sizeof(buf), "%02d:%02d", t/60, t%60);
    return buf;
}

double dist(const City& a, const City& b) {
    double dx=a.x-b.x, dy=a.y-b.y;
    return sqrt(dx*dx+dy*dy);
}

int flightTime(double d) {
    double raw = 60.0*d/800.0 + 40.0;
    return (int)(ceil(raw/5.0))*5;
}

int selectHub(int N, const vector<City>& cities) {
    int best=0; double bestAvg=1e18;
    for (int h=0; h<N; h++) {
        double total=0;
        for (int j=0; j<N; j++) if(j!=h) total+=dist(cities[h],cities[j]);
        double avg=total/(N-1);
        if (avg<bestAvg) { bestAvg=avg; best=h; }
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, R; cin>>N>>R;
    vector<City> cities(N);
    for (auto& c : cities) cin>>c.x>>c.y>>c.w;

    int M; cin>>M;
    for (int i=0; i<M; i++) { int a,b; string s,t; cin>>a>>s>>b>>t; }

    int K; cin>>K;

    int hub = selectHub(N, cities);

    vector<int> spokes;
    for (int i=0; i<N; i++) if(i!=hub) spokes.push_back(i);
    int S = (int)spokes.size();

    vector<int> ft(N, 0);
    for (int s : spokes) ft[s] = flightTime(dist(cities[hub], cities[s]));

    // 各便を (from, dep, to, arr) で表す
    struct Flight { int from, dep, to, arr; };
    vector<vector<Flight>> schedule(K);

    // 各機の状態
    struct PlaneState {
        int city;   // 現在いる都市
        int avail;  // 次に出発できる時刻
    };
    vector<PlaneState> planes(K, {hub, TIME_START});

    // フェーズ1: spoke -> hub のキュー（未完了）
    // フェーズ2: hub -> spoke のキュー（未完了）
    // 順序は ft の小さい順（早く終わるものから）でも可だが
    // ここではシンプルにspokesの順番通りにキューに入れる

    queue<int> ph1_queue, ph2_queue;
    for (int s : spokes) ph1_queue.push(s);
    for (int s : spokes) ph2_queue.push(s);

    // グリーディ割り当て:
    // 各機について「次にできる仕事」を割り当てる
    // 仕事の種類:
    //   - hubにいる場合:
    //       フェーズ1残あり → hub->spoke_x (フェーズ1のための配置便)
    //       フェーズ2残あり → hub->spoke_z (フェーズ2)
    //   - spokeにいる場合:
    //       フェーズ1残あり → spoke->hub (フェーズ1)
    //
    // 戦略:
    //   機がhubにいる場合:
    //     フェーズ1残があれば → hub->spoke_x へ飛んでフェーズ1担当
    //     フェーズ1が全部終わっている → hub->spoke_z でフェーズ2
    //   機がspokeにいる場合:
    //     → spoke->hub (フェーズ1完了) → hubに戻り次の仕事へ

    // シミュレーション: イベント駆動
    // priority_queue で「最も早く空く機」から処理

    // ph1_pending: まだhubへ運んでいないspoke集合
    // ph2_pending: まだhubから飛んでいないspoke集合
    set<int> ph1_pending(spokes.begin(), spokes.end());
    set<int> ph2_pending(spokes.begin(), spokes.end());

    // 機をavail時刻の昇順で処理
    // min-heap: (avail, plane_id)
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    for (int p=0; p<K; p++) pq.push({TIME_START, p});

    while (!pq.empty() && (!ph1_pending.empty() || !ph2_pending.empty())) {
        auto [t, p] = pq.top(); pq.pop();

        int city = planes[p].city;

        if (city == hub) {
            // hubにいる
            // フェーズ1残があれば → spoke_xへ配置便を飛ばす
            if (!ph1_pending.empty()) {
                int target = *ph1_pending.begin();
                ph1_pending.erase(ph1_pending.begin());
                int f = ft[target];
                int dep = t;
                int arr = dep + f;
                if (arr > TIME_END) {
                    // 時間切れ: フェーズ1断念
                    // フェーズ2へ
                    if (!ph2_pending.empty()) {
                        int s2 = *ph2_pending.begin();
                        ph2_pending.erase(ph2_pending.begin());
                        int f2 = ft[s2];
                        int dep2 = t;
                        int arr2 = dep2 + f2;
                        if (arr2 <= TIME_END) {
                            schedule[p].push_back({hub, dep2, s2, arr2});
                            planes[p] = {s2, arr2};
                            pq.push({arr2, p});
                        }
                    }
                } else {
                    // hub -> spoke_x (配置便)
                    schedule[p].push_back({hub, dep, target, arr});
                    planes[p] = {target, arr};
                    pq.push({arr, p});
                }
            } else if (!ph2_pending.empty()) {
                // フェーズ2: hub -> spoke_z
                int s = *ph2_pending.begin();
                ph2_pending.erase(ph2_pending.begin());
                int f = ft[s];
                int dep = t;
                int arr = dep + f;
                if (arr <= TIME_END) {
                    schedule[p].push_back({hub, dep, s, arr});
                    planes[p] = {s, arr};
                    pq.push({arr, p});
                }
            }
        } else {
            // spokeにいる → hub へフェーズ1便
            int s = city;
            int f = ft[s];
            int dep = t;
            int arr = dep + f;
            if (arr <= TIME_END) {
                schedule[p].push_back({s, dep, hub, arr});
                planes[p] = {hub, arr};
                pq.push({arr, p});
            }
        }
    }

    // 出力
    for (int p=0; p<K; p++) {
        cout << schedule[p].size() << "\n";
        for (auto& fl : schedule[p])
            cout << fl.from+1 << " " << fmt(fl.dep) << " "
                 << fl.to+1   << " " << fmt(fl.arr) << "\n";
    }

    return 0;
}