結果
問題 | No.2366 登校 |
ユーザー | vjudge1 |
提出日時 | 2024-05-05 13:19:07 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,594 bytes |
コンパイル時間 | 2,249 ms |
コンパイル使用メモリ | 210,956 KB |
実行使用メモリ | 13,996 KB |
最終ジャッジ日時 | 2024-05-05 13:19:11 |
合計ジャッジ時間 | 3,707 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | WA | - |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | WA | - |
testcase_13 | AC | 45 ms
7,936 KB |
testcase_14 | AC | 45 ms
8,064 KB |
testcase_15 | AC | 46 ms
8,064 KB |
testcase_16 | AC | 46 ms
7,936 KB |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | AC | 46 ms
7,936 KB |
testcase_22 | WA | - |
testcase_23 | AC | 56 ms
13,876 KB |
testcase_24 | AC | 54 ms
13,748 KB |
testcase_25 | WA | - |
testcase_26 | WA | - |
ソースコード
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") typedef long long ll; const ll INF = 1e18; const ll MOD = 1e9 + 7; const ll MAXN = 80 + 5; const ll LOG = 31; #define vll vector <ll> #define pll pair <ll, ll> #define fi first #define se second #define endl '\n' ll n, m, k, t; pll a [MAXN][MAXN]; ll dis [MAXN][MAXN][2*MAXN]; bool vis [MAXN][MAXN][2*MAXN]; priority_queue <array <ll, 4>, vector <array <ll, 4> > , greater <array <ll, 4> > > pq; void dijk(){ for(ll i = 1; i <= n; i++){ for(ll j = 1; j <= m; j++){ for(ll u = 0; u <= n+m-2; u++){ dis[i][j][u] = INF; vis[i][j][u] = 0; } } } dis[1][1][0] = 0; pq.push({0, 1, 1, 0}); while(!pq.empty()){ auto nw = pq.top(); // cout << nw[0] << " " << nw[1] << " " << nw[2] << " " << nw[3] << endl; pq.pop(); if(vis[nw[1]][nw[2]][nw[3]]) continue; vis[nw[1]][nw[2]][nw[3]] = 1; if(nw[3]+1 <= n+m-2){ if(nw[1]+1 <= n && nw[0] < dis[nw[1]+1][nw[2]][nw[3]+1]){ dis[nw[1]+1][nw[2]][nw[3]+1] = nw[0]; pq.push({nw[0], nw[1]+1, nw[2], nw[3]+1}); } if(nw[1]-1 >= 1 && nw[0] < dis[nw[1]-1][nw[2]][nw[3]+1]){ dis[nw[1]-1][nw[2]][nw[3]+1] = nw[0]; pq.push({nw[0], nw[1]-1, nw[2], nw[3]+1}); } if(nw[2]+1 <= m && nw[0] < dis[nw[1]][nw[2]+1][nw[3]+1]){ dis[nw[1]][nw[2]+1][nw[3]+1] = nw[0]; pq.push({nw[0], nw[1], nw[2]+1, nw[3]+1}); } if(nw[2]-1 >= 1 && nw[0] < dis[nw[1]][nw[2]-1][nw[3]+1]){ dis[nw[1]][nw[2]-1][nw[3]+1] = nw[0]; pq.push({nw[0], nw[1], nw[2]-1, nw[3]+1}); } } if(a[nw[1]][nw[2]].fi != 0){ ll c = a[nw[1]][nw[2]].fi, d = a[nw[1]][nw[2]].se; ll cnt = max(ll(0), nw[3]-c+1); if(nw[0]+d < dis[nw[1]][nw[2]][cnt]){ dis[nw[1]][nw[2]][cnt] = nw[0] + d; pq.push({nw[0] + d, nw[1], nw[2], cnt}); } } } } void solve(){ cin >> n >> m >> k >> t; for(ll i = 1; i <= k; i++){ ll x, y, v, w; cin >> x >> y >> v >> w; a[x][y] = {v, w}; } dijk(); if(dis[n][m][min(t,n+m-2)] != INF) cout << dis[n][m][t] << endl; else cout << -1 << endl; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // ll t; cin >> t; // while(t--){ solve(); // } }