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

• 問題: No.5023 Airlines Optimization
• ユーザー: shogo314
• 提出日時: 2026-02-25 21:30:30
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 17 ms / 1,000 ms
• コード長: 5,017 bytes
• コンパイル時間: 6,274 ms
• コンパイル使用メモリ: 200,348 KB
• 実行使用メモリ: 7,844 KB
• スコア: 35,049,937
• 最終ジャッジ日時: 2026-02-25 21:30:44
• 合計ジャッジ時間: 9,661 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

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

ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>

using namespace std;

const int MIN_TIME = 6 * 60;
const int MAX_TIME = 21 * 60;

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

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

string int_to_time(int t) {
    ostringstream oss;
    oss << setfill('0') << setw(2) << (t / 60) << ":" << setw(2) << (t % 60);
    return oss.str();
}

int ssq[48][48][21];
bool captured[48][48][21];

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

    int N, R; cin >> N >> R;
    vector<City> cities(N);
    for (int i = 0; i < N; ++i) cin >> cities[i].x >> cities[i].y >> cities[i].w;
    
    int M; cin >> M;
    for (int i = 0; i < 48; ++i) for (int j = 0; j < 48; ++j) for (int t = 0; t < 21; ++t) ssq[i][j][t] = -1;
    for (int i = 0; i < M; ++i) {
        int a, b; string s, t; cin >> a >> s >> b >> t;
        int si = (stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3, 2)));
        int ti = (stoi(t.substr(0, 2)) * 60 + stoi(t.substr(3, 2)));
        for (int k = 0; k < 21; ++k) if (ti <= 660 + k * 30) ssq[a][b][k] = max(ssq[a][b][k], si);
    }
    int K; cin >> K;

    vector<vector<Flight>> res(K);
    for (int k = 0; k < K; ++k) {
        // 初期位置を人口上位5都市に集中させる
        int cur_city = (k % 5) + 1; 
        int cur_time = MIN_TIME;

        while (cur_time < MAX_TIME) {
            int best_to = -1, best_s = -1, best_dur = -1;
            double max_val = -1e18; // 評価値

            // 待機時間を長め（120分）まで許容し、ベストな出発タイミングを探る
            for (int wait = 0; wait <= 120; wait += 5) {
                int st = cur_time + wait;
                if (st > MAX_TIME - 45) break;

                for (int nxt = 1; nxt <= N; ++nxt) {
                    if (cur_city == nxt) continue;
                    int dur = get_travel_time(cities[cur_city-1], cities[nxt-1]);
                    int arr = st + dur;
                    if (arr > MAX_TIME) continue;

                    double dx = cities[cur_city-1].x - cities[nxt-1].x, dy = cities[cur_city-1].y - cities[nxt-1].y;
                    if (sqrt(dx*dx + dy*dy) < 250.0) continue;

                    long long current_share_gain = 0;
                    for (int t = 0; t < 21; ++t) {
                        if (arr <= 660 + t * 30 && !captured[cur_city][nxt][t]) {
                            if (st > ssq[cur_city][nxt][t]) {
                                current_share_gain += cities[cur_city-1].w * cities[nxt-1].w;
                            }
                        }
                    }

                    // --- 時空間評価ロジック ---
                    double evaluation = (double)current_share_gain;
                    
                    // 1. 時間帯ボーナス: 夕方(16:00-19:00)の便は価値を高める
                    if (st >= 16 * 60 && st <= 19 * 60) evaluation *= 1.3;
                    
                    // 2. ハブ滞在ボーナス: 目的地が人口の多い都市なら、将来の選択肢が広がるため加点
                    double hub_potential = (double)cities[nxt-1].w / 1e6; 
                    evaluation += hub_potential * 10.0; 

                    // 3. 待機ペナルティ: 待ちすぎると効率が落ちるが、利益が大きいなら待つ価値あり
                    evaluation -= (double)wait * 0.5;

                    if (evaluation > max_val) {
                        max_val = evaluation; best_to = nxt; best_s = st; best_dur = dur;
                    }
                }
            }

            if (best_to != -1 && max_val > 0) {
                res[k].push_back({cur_city, best_to, best_s, best_s + best_dur});
                for (int t = 0; t < 21; ++t) {
                    if (best_s + best_dur <= 660 + t * 30 && best_s > ssq[cur_city][best_to][t]) 
                        captured[cur_city][best_to][t] = true;
                }
                cur_city = best_to; cur_time = best_s + best_dur;
            } else {
                // 良い便がない場合、最も人口の多い都市(1)へ移動して次のチャンスを待つ
                if (cur_city == 1) break;
                int dur = get_travel_time(cities[cur_city-1], cities[0]);
                if (cur_time + dur <= MAX_TIME) {
                    res[k].push_back({cur_city, 1, cur_time, cur_time + dur});
                    cur_city = 1; cur_time += dur;
                } else break;
            }
        }
    }

    for (int k = 0; k < K; ++k) {
        cout << res[k].size() << "\n";
        for (auto& f : res[k]) cout << f.from << " " << int_to_time(f.s) << " " << f.to << " " << int_to_time(f.t) << "\n";
    }
    return 0;
}