#1149290 (Python3) No.5023 Airlines Optimization

• 問題: No.5023 Airlines Optimization
• ユーザー: prussian_coder
• 提出日時: 2026-02-25 21:21:45
• 言語: Python3 (3.14.3 + numpy 2.4.2 + scipy 1.17.0)
• 結果: RE
• 実行時間: -
• コード長: 6,292 bytes
• コンパイル時間: 684 ms
• コンパイル使用メモリ: 20,828 KB
• 実行使用メモリ: 20,980 KB
• スコア: 0
• 最終ジャッジ日時: 2026-02-25 21:22:32
• 合計ジャッジ時間: 43,522 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

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

ソースコード

import sys, heapq
from math import sqrt, ceil
from ortools.sat.python import cp_model

def main():
    data = sys.stdin.buffer.read().split()
    p = 0
    def ri(): nonlocal p; v=int(data[p]); p+=1; return v
    def rt(): nonlocal p; h,m=map(int,data[p].split(b':')); p+=1; return h*60+m

    N=ri(); R=ri()
    CX=[0]*N; CY=[0]*N; CW=[0]*N
    for i in range(N): CX[i]=ri(); CY[i]=ri(); CW[i]=ri()

    M=ri()
    SQF=[]
    for _ in range(M):
        a=ri()-1; s=rt(); b=ri()-1; t=rt()
        SQF.append((a,s,b,t))
    K=ri()

    THR = 0.25*R  # 距離閾値=250
    TGT = list(range(660, 1261, 30)); NT=21  # 目標到着時刻21通り

    def edist(i,j): return sqrt((CX[i]-CX[j])**2+(CY[i]-CY[j])**2)
    def fdur(i,j):  return int(ceil((60*edist(i,j)/800+40)/5))*5

    DUR = [[fdur(i,j) if i!=j else 0 for j in range(N)] for i in range(N)]

    # ── Step 1: Square航空の最遅出発時刻を後ろ向きDijkstraで計算 ──────────
    # SSQ[j][ti][i] = 「城市iを出発してTGT[ti]までにjに着くSquare便の最遅出発時刻」
    rev = [[] for _ in range(N)]
    for a,s,b,t in SQF: rev[b].append((a,s,t))

    NEG = -10**9
    SSQ = [[[NEG]*N for _ in range(NT)] for _ in range(N)]

    for j in range(N):
        for ti, ttgt in enumerate(TGT):
            lat=[NEG]*N; lat[j]=ttgt
            h=[(-ttgt, j)]
            while h:
                nt,c=heapq.heappop(h); tc=-nt
                if tc<lat[c]: continue
                for a,s,tf in rev[c]:
                    if tf<=tc and s>lat[a]:
                        lat[a]=s; heapq.heappush(h,(-s,a))
            for i in range(N): SSQ[j][ti][i]=lat[i]

    # ── Step 2: Circle航空の候補直行便を生成 ────────────────────────────────
    # 各(i→j)について「Squareより遅く出発 かつ 指定時刻に到着」できる便を列挙
    CANDS = []
    for i in range(N):
        for j in range(N):
            if i==j or edist(i,j)<THR: continue
            d=DUR[i][j]; w=CW[i]*CW[j]
            tv=[]
            for s in range(360, 1261-d+1, 5):
                v=sum(w for ti,t in enumerate(TGT) if s+d<=t and s>SSQ[j][ti][i])
                if v>0: tv.append((v,s))
            if not tv: continue
            tv.sort(reverse=True)
            for v,s in tv[:3]:  # 各ペアから上位3時刻を採用
                CANDS.append((i, s, j, s+d, v))

    CANDS.sort(key=lambda x:-x[4])
    CANDS=CANDS[:80]; F=len(CANDS)  # 上位80便に絞る

    if F==0:
        for _ in range(K): print(0)
        return

    # ── Step 3: 接続可能性の事前計算 ────────────────────────────────────────
    # COMP[f1][f2] = True: f1到着地==f2出発地 かつ f1到着時刻<=f2出発時刻
    COMP=[[False]*F for _ in range(F)]
    for f1 in range(F):
        _,_,j1,t1,_=CANDS[f1]
        for f2 in range(F):
            i2,s2,_,_,_=CANDS[f2]
            if f1!=f2 and j1==i2 and t1<=s2: COMP[f1][f2]=True

    # 各クエリ(i,j,ti)を勝てる候補便を列挙
    QW={}; QV={}
    for fi,(i,s,j,ta,_) in enumerate(CANDS):
        w=CW[i]*CW[j]
        for ti,t in enumerate(TGT):
            if ta<=t and s>SSQ[j][ti][i]:
                key=(i,j,ti)
                if key not in QW: QW[key]=[]; QV[key]=w
                QW[key].append(fi)

    # ── Step 4: CP-SAT モデル ────────────────────────────────────────────────
    model=cp_model.CpModel()

    # x[k][f] = 機体kが便fを運航するか
    x=[[model.NewBoolVar(f'x{k}_{f}') for f in range(F)] for k in range(K)]

    # 各便は最大1機が運航
    for f in range(F):
        model.Add(sum(x[k][f] for k in range(K))<=1)

    # used[f] = いずれかの機体が運航するか
    used=[model.NewBoolVar(f'u{f}') for f in range(F)]
    for f in range(F):
        model.AddMaxEquality(used[f],[x[k][f] for k in range(K)])

    # AddCircuit: 各機体の便を「接続した一連の経路」に強制
    #
    #   ノード0 = デポ（機体の始発/終着）
    #   ノードf+1 = 便f
    #   弧(f+1, f+1, nx) = 便fをこの機体でスキップ（nx=1-x[k][f]）
    #   弧(0, f+1) = 最初の便
    #   弧(f+1, 0) = 最後の便
    #   弧(f1+1, f2+1) = f2がf1の直後（COMP[f1][f2]=Trueのとき）
    #
    for k in range(K):
        arcs=[(0, 0, model.NewBoolVar(f'i{k}'))]  # 機体k全便なし
        for f in range(F):
            nx=model.NewBoolVar(f'n{k}_{f}')
            model.Add(nx+x[k][f]==1)  # スキップ or 運航
            arcs+=[(f+1,f+1,nx),
                   (0,   f+1, model.NewBoolVar(f's{k}_{f}')),
                   (f+1, 0,   model.NewBoolVar(f'e{k}_{f}'))]
        for f1 in range(F):
            for f2 in range(F):
                if COMP[f1][f2]:
                    arcs.append((f1+1, f2+1, model.NewBoolVar(f't{k}_{f1}_{f2}')))
        model.AddCircuit(arcs)

    # 目的関数: クエリごとにCircleが勝てる場合のw_i*w_j合計を最大化
    obj=[]
    for key,fls in QW.items():
        wq=model.NewBoolVar(f'q{key}')
        model.AddMaxEquality(wq,[used[f] for f in fls])  # OR: どれか1便でも運航なら勝ち
        obj.append(int(QV[key])*wq)
    if obj: model.Maximize(sum(obj))

    solver=cp_model.CpSolver()
    solver.parameters.max_time_in_seconds=0.85
    solver.parameters.num_search_workers=4
    status=solver.Solve(model)

    # ── 出力 ─────────────────────────────────────────────────────────────────
    def fmt(t): return f'{t//60:02d}:{t%60:02d}'
    out=[]
    for k in range(K):
        ok = status in (cp_model.OPTIMAL, cp_model.FEASIBLE)
        fs = sorted([f for f in range(F) if ok and solver.Value(x[k][f])],
                    key=lambda f: CANDS[f][1])  # 出発時刻順（= 唯一の有効順序）
        out.append(str(len(fs)))
        for f in fs:
            i,s,j,ta,_=CANDS[f]
            out.append(f'{i+1} {fmt(s)} {j+1} {fmt(ta)}')
    print('\n'.join(out))

main()