結果
問題 | No.1283 Extra Fee |
ユーザー | hamamu |
提出日時 | 2020-11-06 22:41:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 191 ms / 2,000 ms |
コード長 | 5,845 bytes |
コンパイル時間 | 2,284 ms |
コンパイル使用メモリ | 223,544 KB |
実行使用メモリ | 24,952 KB |
最終ジャッジ日時 | 2023-08-10 06:04:08 |
合計ジャッジ時間 | 6,401 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,384 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,384 KB |
testcase_06 | AC | 2 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,384 KB |
testcase_09 | AC | 2 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 10 ms
4,672 KB |
testcase_12 | AC | 11 ms
4,548 KB |
testcase_13 | AC | 8 ms
4,380 KB |
testcase_14 | AC | 31 ms
7,028 KB |
testcase_15 | AC | 48 ms
9,308 KB |
testcase_16 | AC | 10 ms
4,524 KB |
testcase_17 | AC | 173 ms
23,472 KB |
testcase_18 | AC | 173 ms
22,872 KB |
testcase_19 | AC | 181 ms
24,204 KB |
testcase_20 | AC | 171 ms
22,792 KB |
testcase_21 | AC | 181 ms
23,320 KB |
testcase_22 | AC | 156 ms
21,020 KB |
testcase_23 | AC | 166 ms
24,640 KB |
testcase_24 | AC | 183 ms
24,620 KB |
testcase_25 | AC | 185 ms
24,952 KB |
testcase_26 | AC | 191 ms
24,844 KB |
testcase_27 | AC | 188 ms
24,820 KB |
testcase_28 | AC | 190 ms
24,808 KB |
testcase_29 | AC | 191 ms
24,924 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; using ll=long long; using dd=double; using vll=vector< ll>; using vdd=vector< dd>; using vvll=vector< vll>; using vvdd=vector<vdd>; using vvvll=vector< vvll>; using vvvvll=vector<vvvll>; using pll=pair<ll,ll>; using tll=tuple<ll,ll,ll>; using qll=tuple<ll,ll,ll,ll>; using vpll=vector< pll>; using vtll=vector< tll>; using vqll=vector< qll>; using vvpll=vector<vpll>; using vvtll=vector<vtll>; using vvqll=vector<vqll>; constexpr ll INF = 1LL << 60; struct Fast{ Fast(){ cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(numeric_limits<double>::max_digits10); } } fast; #define REPS(i, S, E) for (ll i = (S); i <= (E); i++) #define REP(i, N) REPS(i, 0, (N)-1) #define DEPS(i, S, E) for (ll i = (E); i >= (S); i--) #define DEP(i, N) DEPS(i, 0, (N)-1) #define rep(i, S, E) for (ll i = (S); i <= (E); i++) #define dep(i, E, S) for (ll i = (E); i >= (S); i--) #define each(e, v) for (auto&& e : v) #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; } template<class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; } template<class T> inline T MaxE(vector<T>&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmax(m,v[i]); return m; } template<class T> inline T MinE(vector<T>&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmin(m,v[i]); return m; } template<class T> inline T MaxE(vector<T> &v) { return MaxE(v,0,(ll)v.size()-1); } template<class T> inline T MinE(vector<T> &v) { return MinE(v,0,(ll)v.size()-1); } template<class T> inline T Sum(vector<T> &v,ll S,ll E){ T s=T(); rep(i,S,E)s+=v[i]; return s; } template<class T> inline T Sum(vector<T> &v) { return Sum(v,0,v.size()-1); } template<class T> inline ll sz(T &v){ return (ll)v.size(); } inline ll CEIL(ll a,ll b){ return (a<0) ? -(-a/b) : (a+b-1)/b; } inline ll FLOOR(ll a,ll b){ return -CEIL(-a,b); } template<ll MOD> struct mll_{ ll val; mll_(ll v = 0): val(v % MOD){ if (val < 0) val += MOD; } mll_ operator - () const { return -val; } mll_ operator + (const mll_ &b) const { return val + b.val; } mll_ operator - (const mll_ &b) const { return val - b.val; } mll_ operator * (const mll_ &b) const { return val * b.val; } mll_ operator / (const mll_ &b) const { return mll_(*this) /= b; } mll_ operator + (ll b) const { return *this + mll_(b); } mll_ operator - (ll b) const { return *this - mll_(b); } mll_ operator * (ll b) const { return *this * mll_(b); } friend mll_ operator + (ll a,const mll_ &b) { return b + a; } friend mll_ operator - (ll a,const mll_ &b) { return -b + a; } friend mll_ operator * (ll a,const mll_ &b) { return b * a; } friend mll_ operator / (ll a,const mll_ &b) { return mll_(a)/b; } mll_ &operator += (const mll_ &b) { val=(val+b.val)%MOD; return *this; } mll_ &operator -= (const mll_ &b) { val=(val+MOD-b.val)%MOD; return *this; } mll_ &operator *= (const mll_ &b) { val=(val*b.val)%MOD; return *this; } mll_ &operator /= (const mll_ &b) { ll c=b.val,d=MOD,u=1,v=0; while (d){ ll t = c / d; c -= t * d; swap(c,d); u -= t * v; swap(u,v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } mll_ &operator += (ll b) { return *this += mll_(b); } mll_ &operator -= (ll b) { return *this -= mll_(b); } mll_ &operator *= (ll b) { return *this *= mll_(b); } mll_ &operator /= (ll b) { return *this /= mll_(b); } bool operator == (const mll_ &b) const { return val == b.val; } bool operator != (const mll_ &b) const { return val != b.val; } bool operator == (ll b) const { return *this == mll_(b); } bool operator != (ll b) const { return *this != mll_(b); } friend bool operator == (ll a,const mll_ &b) { return mll_(a) == b.val; } friend bool operator != (ll a,const mll_ &b) { return mll_(a) != b.val; } friend ostream &operator << (ostream &os,const mll_ &a) { return os << a.val; } friend istream &operator >> (istream &is,mll_ &a) { return is >> a.val; } static mll_ Combination(ll a,ll b){ chmin(b,a-b); if (b<0) return mll_(0); mll_ c = 1; rep(i,0,b-1) c *= a-i; rep(i,0,b-1) c /= i+1; return c; } }; using mll = mll_<1000000007LL>; using vmll = std::vector<mll>; using vvmll = std::vector<vmll>; using vvvmll = std::vector<vvmll>; using vvvvmll = std::vector<vvvmll>; #if 0 #include <atcoder/all> using namespace atcoder; #endif vvvll Dijkstra(ll n, vtll &hwc, pll s) { vvll mp(n,vll(n)); each(e,hwc){ ll h,w,c; tie(h,w,c) = e; mp[h][w]=c; } ll ddx[4]={0,1,0,-1}; ll ddy[4]={1,0,-1,0}; const ll M=2; vvvll dist(n,vvll(n,vll(M,INF))); priority_queue<qll, vqll, greater<qll>> Q; Q.push(qll(0, s.first,s.second,0)); dist[s.first][s.second][0] = 0; while (!Q.empty()){ ll d; ll x,y,z; tie(d, x,y,z) = Q.top(); Q.pop(); if (d > dist[x][y][z]) continue; rep(dz,0,M-1){ if (z==1 and dz==1)continue; rep(idx,0,3){ ll dx=ddx[idx]; ll dy=ddy[idx]; ll xx=x+dx; ll yy=y+dy; ll zz=z+dz; if (xx<0 or n<=xx or yy<0 or n<=yy)continue; ll cost=1; if (dz==0){ cost+=mp[xx][yy]; } if (chmin(dist[xx][yy][zz],dist[x][y][z]+cost)){ Q.push(qll(dist[xx][yy][zz],xx,yy,zz)); } } } } return move(dist); } void solve() { ll n,m; cin >> n >> m; vector<tuple<ll,ll,ll>> hwc(m); rep(i,0,m-1){ ll h; ll w; ll c; cin>>h>>w>>c; hwc[i]={h-1,w-1,c}; } vvvll dist=Dijkstra(n,hwc,{0,0}); ll ans=dist[n-1][n-1][1]; cout << ans << '\n'; } int main(){ #if 1 solve(); //cin2solve(); //generand(); #else ll t; cin >> t; rep(i, 0, t-1){ solve(); //cin2solve(); } #endif return 0; }