#1150594 (C++14) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: ebicochineal
• 提出日時: 2026-02-28 15:56:57
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 813 ms / 1,000 ms
• コード長: 4,095 bytes
• コンパイル時間: 1,308 ms
• コンパイル使用メモリ: 121,060 KB
• 実行使用メモリ: 7,844 KB
• スコア: 12,440,947
• 最終ジャッジ日時: 2026-02-28 15:58:30
• 合計ジャッジ時間: 88,384 ms
• ジャッジサーバーID （参考情報）: judge2 / judge7

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

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <random>
#include <chrono>
#include <cstdio>

using namespace std;

const int INF = -1e9;
const int TIME_MIN = 6 * 60;
const int TIME_MAX = 21 * 60;

struct City { int id; long long x, y, w; };
struct Flight { int from, to, s, t; };

int to_min(int h, int m) { return h * 60 + m; }

int calc_dur(const City& a, const City& b) {
    double d = sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
    return (int)ceil((60.0 * d / 800.0 + 40.0) / 5.0) * 5;
}

class Solver {
    int N, M, K;
    double R;
    vector<City> cities;
    vector<Flight> sq_flights;
    int s_sq[48][48][22];
    vector<vector<Flight>> schedule;

public:
    void solve() {
        if (!(cin >> N >> R)) return;
        cities.resize(N);
        for (int i = 0; i < N; ++i) {
            cities[i].id = i + 1;
            cin >> cities[i].x >> cities[i].y >> cities[i].w;
        }
        
        cin >> M;
        for (int i = 0; i < M; ++i) {
            int a, b, sh, sm, th, tm;
            char c;
            if (!(cin >> a >> sh >> c >> sm >> b >> th >> c >> tm)) break;
            sq_flights.push_back({a, b, to_min(sh, sm), to_min(th, tm)});
        }
        cin >> K;

        for(int i=1; i<=N; ++i) for(int j=1; j<=N; ++j) for(int t=0; t<21; ++t) s_sq[i][j][t] = INF;
        for(int ti=0; ti<21; ++ti) {
            int target_t = to_min(11, 0) + ti * 30;
            for(int j=1; j<=N; ++j) {
                s_sq[j][j][ti] = target_t;
                bool updated = true;
                int cnt = 0;
                while(updated && cnt < N) {
                    updated = false;
                    for(auto& f : sq_flights) {
                        if (f.t <= s_sq[f.to][j][ti]) {
                            if (f.s > s_sq[f.from][j][ti]) {
                                s_sq[f.from][j][ti] = f.s;
                                updated = true;
                            }
                        }
                    }
                    cnt++;
                }
            }
        }

        schedule.resize(K);
        mt19937 engine(42);
        for(int k=0; k<K; ++k) {
            int cur_c = (k % N) + 1;
            int cur_t = TIME_MIN;
            while(cur_t < TIME_MAX) {
                int nxt_c = (engine() % N) + 1;
                if(cur_c == nxt_c) nxt_c = (nxt_c % N) + 1;
                int d = calc_dur(cities[cur_c-1], cities[nxt_c-1]);
                if(cur_t + d > TIME_MAX) break;
                schedule[k].push_back({cur_c, nxt_c, cur_t, cur_t + d});
                cur_t += d;
                cur_c = nxt_c;
            }
        }

        auto start_time = chrono::system_clock::now();
        while (true) {
            auto now = chrono::system_clock::now();
            if (chrono::duration_cast<chrono::milliseconds>(now - start_time).count() > 800) break;

            int k = engine() % K;
            if (schedule[k].empty()) continue;
            int f_idx = engine() % (int)schedule[k].size();

            int old_to = schedule[k][f_idx].to;
            int new_to = (engine() % N) + 1;
            if (new_to == schedule[k][f_idx].from) continue;

            int new_dur = calc_dur(cities[schedule[k][f_idx].from-1], cities[new_to-1]);
            int new_t = schedule[k][f_idx].s + new_dur;

            if (new_t <= TIME_MAX) {
                bool ok = true;
                if (f_idx < (int)schedule[k].size() - 1) {
                    if (new_t > schedule[k][f_idx+1].s || new_to != schedule[k][f_idx+1].from) ok = false;
                }
                if (ok) {
                    schedule[k][f_idx].to = new_to;
                    schedule[k][f_idx].t = new_t;
                }
            }
        }

        for (int k = 0; k < K; ++k) {
            printf("%d\n", (int)schedule[k].size());
            for (auto& f : schedule[k]) {
                printf("%d %02d:%02d %d %02d:%02d\n", f.from, f.s/60, f.s%60, f.to, f.t/60, f.t%60);
            }
        }
    }
};

int main() {
    Solver s;
    s.solve();
    return 0;
}