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

• 問題: No.5023 Airlines Optimization
• ユーザー: Shymohn _
• 提出日時: 2026-02-25 21:49:04
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 4 ms / 1,000 ms
• コード長: 3,205 bytes
• コンパイル時間: 3,969 ms
• コンパイル使用メモリ: 349,292 KB
• 実行使用メモリ: 7,844 KB
• スコア: 11,554,264
• 最終ジャッジ日時: 2026-02-25 21:49:14
• 合計ジャッジ時間: 9,569 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
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;
    // Read and ignore Square airline flights (keep robust: read tokens)
    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;

    // RNG (fixed seed optional for reproducibility)
    std::mt19937_64 rng((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    // std::mt19937_64 rng(12345); // <- 再現性が欲しいならこちらを使う

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

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

    // For each plane, pick a random start city, then keep flying until no next city fits in remaining time
    for(int k=0;k<K;k++){
        uniform_int_distribution<int> uni(0, N-1);
        int cur = uni(rng);
        int time = START;
        while(true){
            // prepare shuffled list of candidate next cities
            vector<int> cand(N);
            iota(cand.begin(), cand.end(), 0);
            shuffle(cand.begin(), cand.end(), rng);
            bool found = false;
            for(int idx = 0; idx < N; ++idx){
                int nxt = cand[idx];
                if(nxt == cur) continue;
                int tt = travel_time_minutes(cities[cur].x, cities[cur].y, cities[nxt].x, cities[nxt].y);
                int dep = time; // depart as soon as possible (time is always multiple of 5)
                int arr = dep + tt;
                if(arr > END) continue; // can't arrive before end of service
                // accept this flight
                schedules[k].push_back({cur, dep, nxt, arr});
                cur = nxt;
                time = arr;
                found = true;
                break;
            }
            if(!found) break; // no reachable next city within remaining time
        }
    }

    // Output per problem spec: for each aircraft 1..K, print c_i then the flights
    for(int k=0;k<K;k++){
        // print number of flights (possibly zero)
        cout << schedules[k].size() << '\n';
        for(const auto &f : schedules[k]){
            // output 1-based city indices and zero-padded times
            cout << (f.a + 1) << " " << fmt_time(f.dep) << " " << (f.b + 1) << " " << fmt_time(f.arr) << '\n';
        }
        // NO extra newline here
    }

    return 0;
}