結果
問題 | No.1283 Extra Fee |
ユーザー | kyoprouno |
提出日時 | 2020-11-07 00:47:48 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 632 ms / 2,000 ms |
コード長 | 3,091 bytes |
コンパイル時間 | 2,264 ms |
コンパイル使用メモリ | 197,392 KB |
実行使用メモリ | 99,176 KB |
最終ジャッジ日時 | 2024-04-27 23:29:07 |
合計ジャッジ時間 | 11,086 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
15,208 KB |
testcase_01 | AC | 6 ms
15,164 KB |
testcase_02 | AC | 6 ms
15,196 KB |
testcase_03 | AC | 5 ms
15,072 KB |
testcase_04 | AC | 6 ms
15,140 KB |
testcase_05 | AC | 6 ms
15,132 KB |
testcase_06 | AC | 5 ms
15,232 KB |
testcase_07 | AC | 5 ms
15,180 KB |
testcase_08 | AC | 5 ms
15,188 KB |
testcase_09 | AC | 5 ms
15,192 KB |
testcase_10 | AC | 5 ms
15,224 KB |
testcase_11 | AC | 21 ms
18,744 KB |
testcase_12 | AC | 28 ms
19,644 KB |
testcase_13 | AC | 22 ms
18,320 KB |
testcase_14 | AC | 90 ms
29,808 KB |
testcase_15 | AC | 145 ms
38,688 KB |
testcase_16 | AC | 33 ms
20,128 KB |
testcase_17 | AC | 336 ms
73,088 KB |
testcase_18 | AC | 550 ms
91,444 KB |
testcase_19 | AC | 608 ms
96,368 KB |
testcase_20 | AC | 568 ms
91,360 KB |
testcase_21 | AC | 574 ms
92,440 KB |
testcase_22 | AC | 507 ms
84,336 KB |
testcase_23 | AC | 531 ms
98,980 KB |
testcase_24 | AC | 600 ms
98,976 KB |
testcase_25 | AC | 632 ms
99,176 KB |
testcase_26 | AC | 623 ms
99,032 KB |
testcase_27 | AC | 627 ms
99,060 KB |
testcase_28 | AC | 631 ms
99,096 KB |
testcase_29 | AC | 370 ms
77,652 KB |
ソースコード
#pragma GCC optimize("O3") #include <bits/stdc++.h> #define ll long long #define rep(i,n) for(ll i=0;i<(n);i++) #define pll pair<ll,ll> #define pii pair<int,int> #define pq priority_queue #define pb push_back #define eb emplace_back #define fi first #define se second #define endl '\n' #define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define lb(c,x) distance(c.begin(),lower_bound(all(c),x)) #define ub(c,x) distance(c.begin(),upper_bound(all(c),x)) using namespace std; inline int topbit(unsigned long long x){ return x?63-__builtin_clzll(x):-1; } inline int popcount(unsigned long long x){ return __builtin_popcountll(x); } inline int parity(unsigned long long x){//popcount%2 return __builtin_parity(x); } template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;} template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} const ll INF=1e18; const ll white=0; //未探索 const ll gray=1; //探索中 const ll black=2; //探索済み vector<pll> g[500005]; ll v,r; vector<ll> d; void dijkstra(){ priority_queue<pll> PQ; vector<ll> color(v); rep(i,v){ d[i]=INF; color[i]=white; } d[r]=0; PQ.push(make_pair(0,r)); color[r]=gray; while(!PQ.empty()){ pll f=PQ.top(); PQ.pop(); ll u=f.second; color[u]=black; if(d[u]<f.first*(-1)) continue; //d[u]は正。 for(ll j=0;j<g[u].size();j++){ ll v=g[u][j].first; if(color[v]==black) continue; if(d[v]>d[u]+g[u][j].second){ d[v]=d[u]+g[u][j].second; PQ.push(make_pair(d[v]*(-1),v)); color[v]=gray; } } } } ll dx[4]={-1,1,0,0}; ll dy[4]={0,0,-1,1}; int main(){ ll n,m; cin >> n >> m; vector<ll> h(m),w(m),c(m); map<pll,ll> e; rep(i,m){ cin >> h[i] >> w[i] >> c[i]; h[i]--; w[i]--; e[make_pair(h[i],w[i])]=c[i]; } v=2*n*n; d=vector<ll>(v,INF); rep(i,n){ rep(j,n){ ll now=i*n+j; if(!e.count({i,j})){ rep(k,4){ ll nx=i+dx[k]; ll ny=j+dy[k]; ll from=nx*n+ny; if(0<=nx && nx<=n-1 && 0<=ny && ny<=n-1){ g[from].push_back({now,1LL}); g[from+n*n].push_back({now+n*n,1LL}); } } } else{ ll cost=e[{i,j}]; rep(k,4){ ll nx=i+dx[k]; ll ny=j+dy[k]; ll from=nx*n+ny; if(0<=nx && nx<=n-1 && 0<=ny && ny<=n-1){ g[from].push_back({now,cost+1}); g[from+n*n].push_back({now+n*n,cost+1}); g[from].push_back({now+n*n,1}); } } } } } dijkstra(); ll ans=INF; ans=min(d[n*n-1],d[2*n*n-1]); cout << ans << endl; return 0; }