結果
問題 | No.1283 Extra Fee |
ユーザー | umezo |
提出日時 | 2020-11-07 07:19:55 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 347 ms / 2,000 ms |
コード長 | 2,002 bytes |
コンパイル時間 | 2,040 ms |
コンパイル使用メモリ | 213,768 KB |
実行使用メモリ | 52,292 KB |
最終ジャッジ日時 | 2024-04-27 23:33:32 |
合計ジャッジ時間 | 7,514 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,812 KB |
testcase_01 | AC | 1 ms
6,944 KB |
testcase_02 | AC | 1 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 1 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 1 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | AC | 1 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 12 ms
6,940 KB |
testcase_12 | AC | 16 ms
6,940 KB |
testcase_13 | AC | 12 ms
6,940 KB |
testcase_14 | AC | 55 ms
12,032 KB |
testcase_15 | AC | 88 ms
17,024 KB |
testcase_16 | AC | 19 ms
6,940 KB |
testcase_17 | AC | 220 ms
48,216 KB |
testcase_18 | AC | 313 ms
46,868 KB |
testcase_19 | AC | 333 ms
48,708 KB |
testcase_20 | AC | 326 ms
45,892 KB |
testcase_21 | AC | 332 ms
46,680 KB |
testcase_22 | AC | 296 ms
42,084 KB |
testcase_23 | AC | 290 ms
50,040 KB |
testcase_24 | AC | 347 ms
50,164 KB |
testcase_25 | AC | 346 ms
50,168 KB |
testcase_26 | AC | 346 ms
50,288 KB |
testcase_27 | AC | 344 ms
50,284 KB |
testcase_28 | AC | 343 ms
50,260 KB |
testcase_29 | AC | 239 ms
52,292 KB |
ソースコード
#define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; #include <bits/stdc++.h> using namespace std; const ll INF=1LL<<60; struct Edge{ int to; ll w; Edge(int to,ll w) : to(to),w(w) {} }; using Graph=vector<vector<Edge>>; using pli=pair<ll,int>; ll A[510][510]; template<class T> bool chmin(T& a,T b){ if(a>b){ a=b; return true; } return false; } int main(){ int n,m; cin>>n>>m; Graph G(n*n); rep(i,m){ int h,w; ll c; cin>>h>>w>>c; h--,w--; A[h][w]=c; } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(i>0){ G[(i-1)*n+j].push_back(Edge(i*n+j,A[i][j]+1)); G[i*n+j].push_back(Edge((i-1)*n+j,A[i-1][j]+1)); } if(i<n-1){ G[(i+1)*n+j].push_back(Edge(i*n+j,A[i][j]+1)); G[i*n+j].push_back(Edge((i+1)*n+j,A[i+1][j]+1)); } if(j>0){ G[i*n+j-1].push_back(Edge(i*n+j,A[i][j]+1)); G[i*n+j].push_back(Edge(i*n+j-1,A[i][j-1]+1)); } if(j<n-1){ G[i*n+j+1].push_back(Edge(i*n+j,A[i][j]+1)); G[i*n+j].push_back(Edge(i*n+j+1,A[i][j+1]+1)); } } } vector<ll> dist(n*n,INF),dist1(n*n,INF); dist[0]=0,dist1[n*n-1]=0; priority_queue<pli,vector<pli>,greater<pli>> que,que1; que.push({dist[0],0}); que1.push({dist1[n*n-1],n*n-1}); while(!que.empty()){ int v=que.top().second; ll d=que.top().first; que.pop(); if(d>dist[v]) continue; for(auto e:G[v]){ if(chmin(dist[e.to],dist[v]+e.w)){ que.push({dist[e.to],e.to}); } } } while(!que1.empty()){ int v=que1.top().second; ll d=que1.top().first; que1.pop(); if(d>dist1[v]) continue; for(auto e:G[v]){ if(chmin(dist1[e.to],dist1[v]+e.w)){ que1.push({dist1[e.to],e.to}); } } } ll mi=INF; rep(i,n){ rep(j,n){ mi=min(mi,dist[i*n+j]+dist1[i*n+j]-2*A[i][j]); } } cout<<mi<<endl; return 0; }