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

• 問題: No.5023 Airlines Optimization
• ユーザー: ebicochineal
• 提出日時: 2026-02-28 17:02:25
• 言語: C++14 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 906 ms / 1,000 ms
• コード長: 3,996 bytes
• コンパイル時間: 6,458 ms
• コンパイル使用メモリ: 125,232 KB
• 実行使用メモリ: 7,848 KB
• スコア: 33,100,379
• 最終ジャッジ日時: 2026-02-28 17:04:12
• 合計ジャッジ時間: 98,721 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

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

ソースコード

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

using namespace std;

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 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<vector<Flight>> schedule;

public:
    void solve() {
        if (!(cin >> N >> R)) return;
        cities.resize(N);
        for (int i = 0; i < N; ++i) 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;
            cin >> a >> sh >> c >> sm >> b >> th >> c >> tm;
        }
        cin >> K;
        int best_hub = 1;
        long long max_pot = -1;

        for (int h = 1; h <= N; ++h) {
            long long pot = 0;
            for (int s = 1; s <= N; ++s) {
                if (h == s) continue;
                double dx = cities[h-1].x - cities[s-1].x;
                double dy = cities[h-1].y - cities[s-1].y;
                if (sqrt(dx*dx + dy*dy) < 0.25 * R) continue;
                int d = calc_dur(cities[h-1], cities[s-1]);
                pot += (cities[h-1].w * cities[s-1].w) / d;
            }
            if (pot > max_pot) {
                max_pot = pot;
                best_hub = h;
            }
        }

        schedule.resize(K);
        mt19937 engine(42);
        vector<int> pop_sorted;
        for(int i=1; i<=N; ++i) if(i != best_hub) pop_sorted.push_back(i);
        sort(pop_sorted.begin(), pop_sorted.end(), [&](int a, int b){
            return cities[a-1].w > cities[b-1].w;
        });

        for (int k = 0; k < K; ++k) {
            int u = best_hub;
            int v = pop_sorted[k % pop_sorted.size()];
            double dx = cities[u-1].x - cities[v-1].x;
            double dy = cities[u-1].y - cities[v-1].y;
            if (sqrt(dx*dx + dy*dy) < 0.25 * R) {
                v = pop_sorted[(k + K) % pop_sorted.size()];
            }

            int cur_t = TIME_MIN;
            int cur_loc = u;
            while (true) {
                int dest = (cur_loc == u) ? v : u;
                int d = calc_dur(cities[cur_loc - 1], cities[dest - 1]);
                if (cur_t + d > TIME_MAX) break;
                schedule[k].push_back({cur_loc, dest, cur_t, cur_t + d});
                cur_t += d;
                cur_loc = dest;
            }
        }
        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() > 900) break;

            int k = engine() % K;
            if (schedule[k].size() < 2) continue;
            
            int f_idx = engine() % schedule[k].size();
            int diff = (engine() % 2 == 0 ? 5 : -5);
            
            int new_s = schedule[k][f_idx].s + diff;
            int new_t = schedule[k][f_idx].t + diff;

            if (new_s >= TIME_MIN && new_t <= TIME_MAX) {
                bool ok = true;
                if (f_idx > 0 && schedule[k][f_idx-1].t > new_s) ok = false;
                if (f_idx < (int)schedule[k].size()-1 && new_t > schedule[k][f_idx+1].s) ok = false;
                if (ok) {
                    schedule[k][f_idx].s = new_s;
                    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;
}