제출 #1283188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283188		abc123	은하철도 (APIO24_train)	C++20	5 / 100	682 ms	10824 KiB

train

#include <bits/stdc++.h>
using namespace std;
struct Edge {int y, a, b; long long c;};
struct State {long long t, cost; int v, mask; bool operator<(const State&o)const{return cost>o.cost;}};

long long solve(int N, int M, int W, vector<int> T, vector<int> X, vector<int> Y,
                vector<int> A, vector<int> B, vector<int> C, vector<int> L, vector<int> R) {
    vector<vector<Edge>> g(N);
    for (int i=0;i<M;i++) g[X[i]].push_back({Y[i],A[i],B[i],C[i]});
    long long INF = 4e18;
    unordered_map<long long,long long> dist;  // encode (v<<10)|mask
    auto key=[&](int v,int m){return ((long long)v<<10)|m;};
    priority_queue<State> pq;
    pq.push({0,0,0,0});
    dist[key(0,0)]=0;

    while(!pq.empty()){
        auto [t,c,v,mask]=pq.top(); pq.pop();
        if(dist[key(v,mask)]<c) continue;
        if(v==N-1 && mask==(1<<W)-1) return c;

        // take meals on planet v if within L/R
        for(int i=0;i<W;i++)
            if(!(mask>>i&1) && L[i]<=t && t<=R[i]){
                int nmask=mask|(1<<i);
                long long nc=c+T[v];
                if(dist[key(v,nmask)]>nc){
                    dist[key(v,nmask)]=nc;
                    pq.push({t,nc,v,nmask});
                }
            }

        // board train
        for(auto&e:g[v]) if(e.a>=t){
            int nmask=mask;
            for(int i=0;i<W;i++)
                if(!(mask>>i&1)&&!(R[i]<e.a||L[i]>e.b))
                    nmask|=1<<i;
            long long nc=c+e.c;
            if(!dist.count(key(e.y,nmask))||dist[key(e.y,nmask)]>nc){
                dist[key(e.y,nmask)]=nc;
                pq.push({e.b,nc,e.y,nmask});
            }
        }
    }
    return -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60