結果
問題 |
No.1283 Extra Fee
|
ユーザー |
![]() |
提出日時 | 2024-04-04 12:36:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 301 ms / 2,000 ms |
コード長 | 1,520 bytes |
コンパイル時間 | 2,934 ms |
コンパイル使用メモリ | 219,072 KB |
最終ジャッジ日時 | 2025-02-20 20:03:40 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template<typename T> using pq = priority_queue<T, vector<T>, greater<T>>; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll N, M, h, w, x, nh, nw, d, alt; bool f; cin >> N >> M; vector c(N, vector<ll>(N)); for (int i=0; i<M; i++){ cin >> h >> w >> x; h--; w--; c[h][w] = x; } pq<tuple<ll, int, int, bool>> que; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; vector dist(N, vector(N, vector<ll>(2, 1e18))); vector vst(N, vector(N, vector<bool>(2, 0))); dist[0][0][0] = 0; que.push({0, 0, 0, 0}); while(!que.empty()){ tie(d, h, w, f) = que.top(); que.pop(); if (vst[h][w][f]) continue; vst[h][w][f] = 1; for (int dir=0; dir<4; dir++){ nh = h + dx[dir]; nw = w + dy[dir]; if (nh < 0 || nh >= N || nw < 0 || nw >= N) continue; alt = dist[h][w][f]+1+c[nh][nw]; if (alt < dist[nh][nw][f]){ dist[nh][nw][f] = alt; que.push({dist[nh][nw][f], nh, nw, f}); } if (f == 0){ alt = dist[h][w][f]+1; if (alt < dist[nh][nw][1]){ dist[nh][nw][1] = alt; que.push({dist[nh][nw][1], nh, nw, 1}); } } } } cout << min(dist[N-1][N-1][0], dist[N-1][N-1][1]) << endl; return 0; }