#1027921 (C++23(gcc13)) No.1 道のショートカット

提出ソース

結果

問題	No.1 道のショートカット
ユーザー	xpic
提出日時	2024-11-22 04:38:05
言語	C++23(gcc13) (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 5,000 ms
コード長	9,154 bytes
コンパイル時間	2,908 ms
コンパイル使用メモリ	214,120 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-11-22 04:38:10
合計ジャッジ時間	4,422 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	3 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	3 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	3 ms 5,248 KB
testcase_12	AC	3 ms 5,248 KB
testcase_13	AC	3 ms 5,248 KB
testcase_14	AC	3 ms 5,248 KB
testcase_15	AC	3 ms 5,248 KB
testcase_16	AC	3 ms 5,248 KB
testcase_17	AC	2 ms 5,248 KB
testcase_18	AC	2 ms 5,248 KB
testcase_19	AC	2 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	2 ms 5,248 KB
testcase_22	AC	2 ms 5,248 KB
testcase_23	AC	3 ms 5,248 KB
testcase_24	AC	2 ms 5,248 KB
testcase_25	AC	2 ms 5,248 KB
testcase_26	AC	2 ms 5,248 KB
testcase_27	AC	3 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	3 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	2 ms 5,248 KB
testcase_33	AC	3 ms 5,248 KB
testcase_34	AC	2 ms 5,248 KB
testcase_35	AC	3 ms 5,248 KB
testcase_36	AC	2 ms 5,248 KB
testcase_37	AC	3 ms 5,248 KB
testcase_38	AC	2 ms 5,248 KB
testcase_39	AC	3 ms 5,248 KB
testcase_40	AC	2 ms 5,248 KB
testcase_41	AC	2 ms 5,248 KB
testcase_42	AC	2 ms 5,248 KB
testcase_43	AC	3 ms 5,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define __GLIBCXX_BITSIZE_INT_N_0 128
#define __GLIBCXX_TYPE_INT_N_0 __int128

#include <algorithm>
#include <array>
#include <concepts>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <filesystem>
#include <iterator>
#include <limits>
#include <string_view>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

namespace fastio {

static constexpr int BUF_SIZE = 1 << 17;

class QI {

private:

    FILE *stream_;
    std::array<char, BUF_SIZE> buf_ = {};
    char *begin_;
    char *end_;
    char *ptr_;

    void skip_space() {
        while (*ptr_ <= ' ') ++ptr_;
    }

    template<int N = 0>
    void read() {
        if (const auto n = end_ - ptr_; n <= N) {
            std::ignore = fread(std::copy_n(ptr_, n, begin_), 1, BUF_SIZE - n, stream_);
            ptr_ = begin_;
        }
    }

    template<std::unsigned_integral T>
    void parse(T &x) {
        std::common_type_t<T, std::uint64_t> x2 = 0;
        while (true) {
            std::uint64_t v;
            std::memcpy(&v, ptr_, 8);
            if ((v -= 0x3030303030303030) & 0x8080808080808080)
                break;
            v = (v * 10 + (v >> 8)) & 0xff00ff00ff00ff;
            v = (v * 100 + (v >> 16)) & 0xffff0000ffff;
            v = (v * 10000 + (v >> 32)) & 0xffffffff;
            x2 = 100000000 * x2 + v;
            ptr_ += 8;
        }
        while (true) {
            std::uint32_t v;
            std::memcpy(&v, ptr_, 4);
            if ((v -= 0x30303030) & 0x80808080)
                break;
            v = (v * 10 + (v >> 8)) & 0xff00ff;
            v = (v * 100 + (v >> 16)) & 0xffff;
            x2 = 10000 * x2 + v;
            ptr_ += 4;
            break;
        }
        while (true) {
            std::uint16_t v;
            std::memcpy(&v, ptr_, 2);
            if ((v -= 0x3030) & 0x8080) break;
            v = (v * 10 + (v >> 8)) & 0xff;
            x2 = 100 * x2 + v;
            ptr_ += 2;
            break;
        }
        if (' ' < *ptr_) {
            x2 *= 10;
            x2 += *ptr_++ - '0';
        }
        ++ptr_;
        x = static_cast<T>(x2);
    }

public:
    QI() : QI(stdin) {}
    explicit QI(const std::filesystem::path& p) : QI(fopen(p.c_str(), "r")) {}
    explicit QI(FILE *stream) : stream_(stream), begin_(buf_.data()), end_(begin_ + BUF_SIZE), ptr_(end_) {
        read();
    }
    ~QI() { if (stream_ != stdin) fclose(stream_); }
    QI(const QI&) = delete;
    QI &operator=(const QI&) = delete;

    template<std::unsigned_integral T>
    void operator()(T &x) {
        skip_space();
        read<64>();
        parse(x);
    }
    template<std::signed_integral T>
    void operator()(T &x) {
        skip_space();
        read<64>();
        std::make_unsigned_t<T> u;
        if (*ptr_ == '-') {
            ++ptr_;
            parse(u);
            u = -u;
        } else {
            parse(u);
        }
        x = u;
    }
    void operator()(char &x) {
        skip_space();
        read<64>();
        x = *ptr_;
        ++ptr_;
    }
    void operator()(std::string &x) {
        x = "";
        skip_space();
        read<64>();
        while (*ptr_ > ' ' && *ptr_ != '\0') {
            x.push_back(*ptr_);
            ++ptr_;
        }
        ++ptr_;
    }
    template<class... Ts> requires(sizeof...(Ts) != 1)
    void operator () (Ts&... xs) {
        ((*this)(xs), ...);
    }
    template<class T>
    QI &operator>>(T &x) { (*this)(x); return *this; }

}; // class QI

class QO {

private:

    FILE *stream_;
    std::array<char, BUF_SIZE> buf_ = {};
    char *begin_;
    char *end_;
    char *ptr_;
    
    template<class T> static constexpr int DIGITS = std::numeric_limits<T>::digits10 + 1;
    template<class T> static constexpr auto POW10 = [] {
        std::array<T, DIGITS<T>> ret;
        ret[0] = 1;
        for (int i = 1; i < DIGITS<T>; ++i) {
            ret[i] = 10 * ret[i - 1];
        }
        return ret;
    } ();
    static constexpr auto LUT = [] {
        std::array<char, 40000> res;
        char* p = res.data();
        char a = '0', b = '0', c = '0', d = '0';
        do {
            *p++ = a, *p++ = b, *p++ = c, *p++ = d;
        } while (d++ < '9' || (d = '0', c++ < '9' || (c = '0', b++ < '9' || (b = '0', a++ < '9'))));
        return res;
    } ();
    
    template<int N = BUF_SIZE> void flush() {
        if (end_ - ptr_ <= N) {
            fwrite(begin_, 1, ptr_ - begin_, stream_);
            ptr_ = begin_;
        }
    }
    
    template<int N = 4> void le4(std::uint64_t x) {
        if constexpr (1 < N) {
            if (x < POW10<std::uint64_t>[N - 1]) {
                le4<N - 1>(x);
                return;
            }
        }
        ptr_ = std::copy_n(&LUT[x * 4 + (4 - N)], N, ptr_);
    }
    template<int N> void w4(std::uint64_t x) {
        if constexpr (0 < N) {
            ptr_ = std::copy_n(&LUT[x / POW10<std::uint64_t>[N - 4] * 4], 4, ptr_);
            w4<N - 4>(x % POW10<std::uint64_t>[N - 4]);
        }
    }
    template<int N> void write(std::uint64_t x) {
        if constexpr (N < DIGITS<std::uint64_t>) {
            if (POW10<std::uint64_t>[N] <= x) {
                write<N + 4>(x);
                return;
            }
        }
        le4(x / POW10<std::uint64_t>[N - 4]);
        w4<N - 4>(x % POW10<std::uint64_t>[N - 4]);
    }
    void write(std::unsigned_integral auto x) {
        write<4>(x);
    }
    void write(__uint128_t x) {
        if (x < POW10<__uint128_t>[16]) {
            write(static_cast<std::uint64_t>(x));
        } else if (x < POW10<__uint128_t>[32]) {
            write(static_cast<std::uint64_t>(x / POW10<__uint128_t>[16]));
            w4<16>(static_cast<std::uint64_t>(x % POW10<__uint128_t>[16]));
        } else {
            write(static_cast<std::uint64_t>(x / POW10<__uint128_t>[32]));
            x %= POW10<__uint128_t>[32];
            w4<16>(static_cast<std::uint64_t>(x / POW10<__uint128_t>[16]));
            w4<16>(static_cast<std::uint64_t>(x % POW10<__uint128_t>[16]));
        }
    }

public:
    
    QO() : QO(stdout) {}
    explicit QO(const std::filesystem::path& p) : QO(fopen(p.c_str(), "w")) {}
    explicit QO(FILE* stream)
    : stream_(stream), begin_(buf_.data()), end_(begin_ + BUF_SIZE), ptr_(begin_) {}
    ~QO() {
        flush();
        if (stream_ != stdout) { fclose(stream_); }
    }
    QO(const QO&) = delete;
    QO& operator = (const QO&) = delete;
    
    template<std::unsigned_integral T> void operator()(T x) {
        flush<DIGITS<T>>();
        write(x);
    }
    template<std::signed_integral T> void operator()(T x) {
        flush<1 + DIGITS<T>>();
        using U = std::make_unsigned_t<T>;
        const U u = x;
        if (x < 0) {
            *ptr_++ = '-';
            write(static_cast<U>(-u));
        }
        else {
            write(u);
        }
    }
    void operator()(char c) {
        flush<1>();
        *ptr_++ = c;
    }
    void operator()(std::string_view s) {
        while (!s.empty()) {
            flush<0>();
            const auto n = std::min(std::ssize(s), end_ - ptr_);
            if (n == BUF_SIZE) {
                fwrite(s.data(), 1, BUF_SIZE, stream_);
            }
            else {
                ptr_ = std::copy_n(s.data(), n, ptr_);
            }
            s.remove_prefix(n);
        }
        flush<0>();
    }
    template <char End = '\n', char Sep = ' ', class T, class... Ts>
    void ln(T&& x, Ts&&... xs) {
        (*this)(forward<T>(x));
        if constexpr (sizeof...(Ts) == 0) {
            *ptr_++ = End;
        }
        else {
            *ptr_++ = Sep;
            ln<End, Sep>(forward<Ts>(xs)...);
        }
    }
    template<class T> QO& operator<<(T x) { (*this)(x); return *this; }

}; // class QO

fastio::QI cin;
fastio::QO cout;

} // namespace fastio

void yuki1() {
    using fastio::cin, fastio::cout;
    using i32 = std::int32_t;
    using u32 = std::uint32_t;
    using i64 = std::int64_t;
    using u64 = std::uint64_t;
    using i128 = __int128_t;
    using u128 = __uint128_t;

    const i32 inf = 1e9+7;
    
    i32 n, c, v;
    cin >> n >> c >> v;
    std::vector<i32> S(v), T(v), Y(v), M(v);
    for (auto &a : S) cin >> a, a--;
    for (auto &a : T) cin >> a, a--;
    for (auto &a : Y) cin >> a;
    for (auto &a : M) cin >> a;
    std::vector<std::vector<std::tuple<i32,i32,i32>>> g(n);
    for (int i = 0; i < v; i++)
        g.at(S.at(i)).push_back({T.at(i), Y.at(i), M.at(i)});
    std::vector<std::vector<i32>> dp(n, std::vector<i32>(c + 1, inf));
    dp.at(0).at(c) = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= c; j++) {
            if (dp.at(i).at(j) == inf)
                continue;
            for (auto [to, cost, time] : g.at(i)) {
                if (j < cost)
                    continue;
                dp.at(to).at(j - cost) = std::min(dp.at(to).at(j - cost), dp.at(i).at(j) + time);
            }
        }
    }
    i32 res = *min_element(dp.at(n - 1).begin(), dp.at(n - 1).end());
    if (res == inf)
        res = -1;
    cout << res << '\n';
}

int main() {
    yuki1();
}

yukicoder

結果

テストケース

ソースコード