結果
問題 | No.2366 登校 |
ユーザー |
![]() |
提出日時 | 2023-06-30 22:22:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 416 ms / 4,000 ms |
コード長 | 2,102 bytes |
コンパイル時間 | 4,012 ms |
コンパイル使用メモリ | 297,312 KB |
実行使用メモリ | 28,160 KB |
最終ジャッジ日時 | 2025-06-20 11:11:11 |
合計ジャッジ時間 | 6,440 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr double EPS = 1e-8; constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1}; constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1}; constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << fixed << setprecision(20); } } iosetup; int main() { int n, m, k, t; cin >> n >> m >> k >> t; const int cons = n - 1 + m - 1; if (t >= cons) { cout << 0 << '\n'; return 0; } vector c(n, vector(m, 0)), d(n, vector(m, 0)); while (k--) { int a, b; cin >> a >> b; --a; --b; cin >> c[a][b] >> d[a][b]; --c[a][b]; } vector dp(n, vector(m, vector(cons * 3 + 1, LINF))); dp[0][0][cons * 2 + t] = 0; priority_queue<tuple<ll, int, int, int>, vector<tuple<ll, int, int, int>>, greater<tuple<ll, int, int, int>>> que; que.emplace(0, 0, 0, cons * 2 + t); while (!que.empty()) { const auto [dp_v, i, j, tm] = que.top(); que.pop(); if (dp_v > dp[i][j][tm]) continue; if (const int ntm = min(tm + c[i][j], cons * 3); chmin(dp[i][j][ntm], dp[i][j][tm] + d[i][j])) { que.emplace(dp[i][j][ntm], i, j, ntm); } if (tm >= 1) { REP(k, 4) { const int y = i + DY4[k], x = j + DX4[k]; if (0 <= y && y < n && 0 <= x && x < m && chmin(dp[y][x][tm - 1], dp[i][j][tm])) { que.emplace(dp[y][x][tm - 1], y, x, tm - 1); } } } } const ll ans = *min_element(next(dp[n - 1][m - 1].begin(), cons * 2), dp[n - 1][m - 1].end()); cout << (ans == LINF ? -1 : ans) << '\n'; return 0; }