제출 #1202459

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202459		Nelt	은하철도 (APIO24_train)	C++20	0 / 100	1096 ms	18880 KiB

train

#include "train.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

long long solve(int n, int m, int w, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C, std::vector<int> L,
                std::vector<int> R)
{
    ll dp[n], ndp[n];
    dp[0] = 0;
    for (ll i = 1; i < n; i++)
        dp[i] = 1e18;
    array<ll, 5> edges[m];
    for (ll i = 0; i < m; i++)
        edges[i] = {X[i], Y[i], A[i], B[i], C[i]};
    sort(edges, edges + m, [&](array<ll, 5> &a, array<ll, 5> &b)
    {
        return a[3] < b[3];
    });
    vector<pair<ll, ll>> cur[n];
    for (ll i = 1; i < n; i++)
        cur[i] = {make_pair((ll)-1, (ll)1e18)};
    cur[0] = {make_pair((ll)-1, 0)};
    L.insert(L.begin(), 0);
    R.insert(R.begin(), 1e9);
    T.insert(T.begin(), 0);
    w++;
    for (ll j = 0; j < w; j++)
    {
        for (ll i = 0; i < n; i++)
            ndp[i] = 1e18, cur[i] = {make_pair((ll)-1, dp[i])};
        for (auto [x, y, a, b, c] : edges)
        {
            for (ll i = 0; i < cur[x].size(); i++)
                if (cur[x][i].first < a)
                {
                    if (R[j] > b)
                        ndp[y] = min({ndp[y], cur[x][i].second + T[j] + c});
                    if (max(a, (ll)L[j]) <= min(b, (ll)R[j]))
                        ndp[y] = min(ndp[y], cur[x][i].second + c);
                    ndp[y] = min(ndp[y], ndp[x] + c);
                }
            ndp[y] = min(ndp[y], dp[y] + T[j] + c);
            cur[y].push_back(make_pair(b, dp[y]));
        }
        for (ll i = 0; i < n; i++)
            dp[i] = ndp[i];
    }
    return dp[n - 1] == 1e18 ? -1 : dp[n - 1];
}

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