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

• 問題: No.5023 Airlines Optimization
• ユーザー: Shymohn _
• 提出日時: 2026-02-25 21:54:53
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 3 ms / 1,000 ms
• コード長: 2,891 bytes
• コンパイル時間: 3,732 ms
• コンパイル使用メモリ: 353,608 KB
• 実行使用メモリ: 7,848 KB
• スコア: 36,438,156
• 最終ジャッジ日時: 2026-02-25 21:55:03
• 合計ジャッジ時間: 8,998 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

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

ソースコード

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

struct City { double x, y; long long w; };
struct Flight { int a; int dep; int b; int arr; }; // times in minutes from midnight

int travel_time_minutes(double x1, double y1, double x2, double y2) {
    double d = hypot(x1 - x2, y1 - y2);
    double raw = 60.0 * d / 800.0 + 40.0;
    int tt = (int)ceil(raw / 5.0) * 5;
    return tt;
}

string fmt_time(int t){
    int hh = t / 60;
    int mm = t % 60;
    char buf[6];
    sprintf(buf, "%02d:%02d", hh, mm);
    return string(buf);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    int R;
    if(!(cin >> N >> R)) return 0;
    vector<City> cities(N);
    for(int i=0;i<N;i++){
        long long xi, yi, wi;
        cin >> xi >> yi >> wi;
        cities[i].x = (double)xi;
        cities[i].y = (double)yi;
        cities[i].w = wi;
    }
    int M;
    cin >> M;
 
    for(int i=0;i<M;i++){
        int a, b;
        string s_str, t_str;
        cin >> a >> s_str >> b >> t_str;
    }
    int K;
    cin >> K;

    const int START = 6*60;   // 360
    const int END   = 21*60;  // 1260

    // Edge: no other cities
    if(N == 0){
        for(int k=0;k<K;k++) cout << 0 << '\n';
        return 0;
    }

    // 1) find hub = city with max population (tie-break by smaller index)
    int hub = 0;
    for(int i=1;i<N;i++){
        if(cities[i].w > cities[hub].w) hub = i;
    }

    // 2) build sorted list of other cities by population desc
    vector<pair<long long,int>> vec;
    for(int i=0;i<N;i++){
        if(i==hub) continue;
        vec.emplace_back(cities[i].w, i);
    }
    sort(vec.begin(), vec.end(), [](const auto &A, const auto &B){
        if(A.first != B.first) return A.first > B.first;
        return A.second < B.second;
    });


    int needSpokes = 25;
    int topCount = min((int)vec.size(), needSpokes);
    vector<int> targets;
    for(int i=0;i<topCount;i++) targets.push_back(vec[i].second);

    vector<vector<Flight>> schedules(K);


    if(topCount == 0){
        for(int k=0;k<K;k++){
            cout << 0 << '\n';
        }
        return 0;
    }


    for(int k=0;k<K;k++){
        int target = targets[k % topCount];
        int cur = hub;
        int time = START;

        while(true){
            int next = (cur == hub) ? target : hub;
            int tt = travel_time_minutes(cities[cur].x, cities[cur].y, cities[next].x, cities[next].y);
            int dep = time;
            int arr = dep + tt;
            if(arr > END) break;
            schedules[k].push_back({cur, dep, next, arr});
            cur = next;
            time = arr;
        }
    }

    for(int k=0;k<K;k++){
        cout << schedules[k].size() << '\n';
        for(const auto &f : schedules[k]){
            cout << (f.a + 1) << " " << fmt_time(f.dep) << " " << (f.b + 1) << " " << fmt_time(f.arr) << '\n';
        }
    }

    return 0;
}