結果
| 問題 | No.1 道のショートカット |
| ユーザー |
 xpic
|
| 提出日時 | 2024-11-22 04:38:05 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 40 |
ソースコード
#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 QIclass 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 QOfastio::QI cin;fastio::QO cout;} // namespace fastiovoid 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();}