結果

問題 No.5023 Airlines Optimization
コンテスト
ユーザー ebicochineal
提出日時 2026-02-28 15:44:36
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 9 ms / 1,000 ms
コード長 2,530 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,348 ms
コンパイル使用メモリ 115,648 KB
実行使用メモリ 7,848 KB
スコア 6,220,235
最終ジャッジ日時 2026-02-28 15:44:48
合計ジャッジ時間 6,773 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using namespace std;

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

struct Flight {
    int from, to, s, t;
};

struct City {
    int id;
    long long x, y, w;
};

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

class Solver {
    int N, M, K;
    double R;
    vector<City> cities;
    vector<vector<Flight>> schedule;

public:
    void read_input() {
        cin >> N >> R;
        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, s_h, s_m, b, t_h, t_m;
            char c; cin >> a >> s_h >> c >> s_m >> b >> t_h >> c >> t_m;
        }
        cin >> K;
        schedule.resize(K);
    }

    void generate_initial_solution() {
        for(int k=0; k<K; ++k) {
            int current_city = (k % N) + 1;
            int current_time = to_min(6, 0);
            
            while(current_time < to_min(20, 0)) {
                int next_city = (current_city == 1 ? 2 : 1);
                int dur = calc_duration(cities[current_city-1], cities[next_city-1]);
                if(current_time + dur > to_min(21, 0)) break;

                schedule[k].push_back({current_city, next_city, current_time, current_time + dur});
                current_time += dur;
                current_city = next_city;
            }
        }
    }
    void solve() {
        mt19937 engine(42);
        double temp = 1000.0;
        double cooldown = 0.9999;

        for (int iter = 0; iter < 100000; ++iter) {
            int k = engine() % K;
            if (schedule[k].empty()) continue;
            int f_idx = engine() % schedule[k].size();
            int old_s = schedule[k][f_idx].s;
            int diff = (engine() % 2 == 0 ? 5 : -5);
            
            temp *= cooldown;
        }
    }

    void output() {
        for(int k=0; k<K; ++k) {
            cout << schedule[k].size() << endl;
            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 solver;
    solver.read_input();
    solver.generate_initial_solution();
    solver.solve();
    solver.output();
    return 0;
}
0