結果
問題 | No.1283 Extra Fee |
ユーザー | hamray |
提出日時 | 2020-11-07 18:11:30 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 182 ms / 2,000 ms |
コード長 | 3,268 bytes |
コンパイル時間 | 1,407 ms |
コンパイル使用メモリ | 170,184 KB |
実行使用メモリ | 15,312 KB |
最終ジャッジ日時 | 2024-04-27 23:37:07 |
合計ジャッジ時間 | 5,082 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
7,768 KB |
testcase_01 | AC | 4 ms
8,928 KB |
testcase_02 | AC | 4 ms
8,028 KB |
testcase_03 | AC | 4 ms
9,308 KB |
testcase_04 | AC | 3 ms
7,644 KB |
testcase_05 | AC | 4 ms
9,056 KB |
testcase_06 | AC | 4 ms
8,416 KB |
testcase_07 | AC | 3 ms
7,516 KB |
testcase_08 | AC | 4 ms
8,680 KB |
testcase_09 | AC | 3 ms
7,912 KB |
testcase_10 | AC | 3 ms
7,652 KB |
testcase_11 | AC | 10 ms
8,384 KB |
testcase_12 | AC | 12 ms
8,900 KB |
testcase_13 | AC | 9 ms
8,268 KB |
testcase_14 | AC | 31 ms
10,356 KB |
testcase_15 | AC | 47 ms
10,840 KB |
testcase_16 | AC | 12 ms
9,536 KB |
testcase_17 | AC | 140 ms
13,668 KB |
testcase_18 | AC | 161 ms
14,464 KB |
testcase_19 | AC | 175 ms
14,988 KB |
testcase_20 | AC | 162 ms
14,628 KB |
testcase_21 | AC | 165 ms
14,712 KB |
testcase_22 | AC | 144 ms
14,148 KB |
testcase_23 | AC | 148 ms
15,308 KB |
testcase_24 | AC | 167 ms
15,176 KB |
testcase_25 | AC | 182 ms
15,180 KB |
testcase_26 | AC | 175 ms
15,312 KB |
testcase_27 | AC | 177 ms
15,176 KB |
testcase_28 | AC | 177 ms
15,308 KB |
testcase_29 | AC | 148 ms
13,672 KB |
ソースコード
#include <bits/stdc++.h> //#include <atcoder/all> //using namespace atcoder; const double pi = 3.141592653589793238462643383279; using namespace std; //typedef //------------------------------------------ typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef pair<int, int> PII; typedef pair<long long, long long> PLL; typedef pair<int, PII> TIII; typedef long long LL; typedef unsigned long long ULL; typedef vector<LL> VLL; typedef vector<VLL> VVLL; //container util //------------------------------------------ #define ALL(a) (a).begin(), (a).endf() #define RALL(a) (a).rbegin(), (a).rend() #define PB push_back #define MP make_pair #define SZ(a) int((a).size()) #define SQ(a) ((a) * (a)) #define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).endf(); ++i) #define EXIST(s, e) ((s).find(e) != (s).endf()) #define SORT(c) sort((c).begin(), (c).endf()) //repetition //------------------------------------------ #define FOR(i, s, n) for (int i = s; i < (int)n; ++i) #define REP(i, n) FOR(i, 0, n) #define MOD 1000000007 #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto &a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; #define chmin(x, y) x = min(x, y) #define chmax(x, y) x = max(x, y) const double EPS = 1e-4, PI = acos(-1); //ここから編集 typedef string::const_iterator State; ll dp[510][510][2]; ll cost[510][510]; int dxy[5]={-1,0,1,0,-1}; int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(6); int N, M; cin >> N >> M; vector<ll> h(M), w(M), c(M); REP(i,510) REP(j,510) REP(k,2) dp[i][j][k] = (1LL<<60); dp[0][0][0] = 0; REP(i,M){ cin >> h[i] >> w[i] >> c[i]; h[i]--; w[i]--; cost[h[i]][w[i]] = c[i]; } priority_queue<pair<ll, pair<ll, int>>,vector<pair<ll, pair<ll, int>>>, greater<pair<ll, pair<ll, int>>>> pq; pq.push(make_pair(0, make_pair(0, 0))); while(pq.size()){ auto p = pq.top(); pq.pop(); int y = p.second.first/N, x = p.second.first%N; ll f = p.second.second; if(dp[y][x][f] < p.first) continue; for(int i=0; i<4; i++){ int ny = y + dxy[i], nx = x + dxy[i+1]; if(ny >= 0 && ny < N && nx >= 0 && nx < N){ if(f==0){ if(dp[ny][nx][1]>dp[y][x][0]+1){ dp[ny][nx][1] = dp[y][x][0]+1; pq.push(make_pair(dp[ny][nx][1], make_pair(ny*N+nx, 1))); } if(dp[ny][nx][0] > dp[y][x][0] + cost[ny][nx]+1){ dp[ny][nx][0] = dp[y][x][0] + cost[ny][nx]+1; pq.push(make_pair(dp[ny][nx][0], make_pair(ny*N+nx, 0))); } }else{ if(dp[ny][nx][1] > dp[y][x][1] + cost[ny][nx]+1){ dp[ny][nx][1] = dp[y][x][1] + cost[ny][nx]+1; pq.push(make_pair(dp[ny][nx][1], make_pair(ny*N+nx, 1))); } } } } } cout << min(dp[N-1][N-1][1], dp[N-1][N-1][0]) << endl; return 0; }