제출 #1283190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283190		abc123	은하철도 (APIO24_train)	C++20	5 / 100	1089 ms	10812 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], (long long)C[i]});
    
    const long long INF = 4e18;
    unordered_map<long long, long long> dist;  // encode state as (v << 10) | mask
    auto key = [&](int v, int mask) { return ((long long)v << 10) | mask; };
    priority_queue<State> pq;
    
    pq.push({0, 0, 0, 0});
    dist[key(0, 0)] = 0;
    
    while (!pq.empty()) {
        auto [time, cost, v, mask] = pq.top(); pq.pop();
        if (dist[key(v, mask)] < cost) continue;
        if (v == N - 1 && mask == (1 << W) - 1) return cost;
        
        // Take meals on planet with cost if in proper meal time window
        for (int i = 0; i < W; i++) {
            if (!(mask & (1 << i)) && L[i] <= time && time <= R[i]) {
                int nmask = mask | (1 << i);
                long long new_cost = cost + T[v];
                if (!dist.count(key(v, nmask)) || dist[key(v, nmask)] > new_cost) {
                    dist[key(v, nmask)] = new_cost;
                    pq.push({time, new_cost, v, nmask});
                }
            }
        }
        
        // Try to take train starting from planet v at/after current time
        for (auto &e : g[v]) {
            if (e.a >= time) {
                int nmask = mask;
                // Meal must lie fully inside train interval to be free
                for (int i = 0; i < W; i++) {
                    if (!(mask & (1 << i)) && L[i] >= e.a && R[i] <= e.b) {
                        nmask |= 1 << i;
                    }
                }
                long long new_cost = cost + e.c;
                if (!dist.count(key(e.y, nmask)) || dist[key(e.y, nmask)] > new_cost) {
                    dist[key(e.y, nmask)] = new_cost;
                    pq.push({e.b, new_cost, e.y, nmask});
                }
            }
        }
    }
    return -1;
}

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