結果
問題 | No.34 砂漠の行商人 |
ユーザー |
![]() |
提出日時 | 2017-08-25 10:28:57 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 25 ms / 5,000 ms |
コード長 | 3,437 bytes |
コンパイル時間 | 2,156 ms |
コンパイル使用メモリ | 197,496 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-06-28 10:37:34 |
合計ジャッジ時間 | 3,147 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 3 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 5 ms
5,376 KB |
testcase_05 | AC | 6 ms
5,376 KB |
testcase_06 | AC | 5 ms
5,376 KB |
testcase_07 | AC | 5 ms
5,376 KB |
testcase_08 | AC | 14 ms
6,528 KB |
testcase_09 | AC | 10 ms
6,016 KB |
testcase_10 | AC | 8 ms
6,144 KB |
testcase_11 | AC | 10 ms
6,272 KB |
testcase_12 | AC | 5 ms
5,376 KB |
testcase_13 | AC | 25 ms
8,064 KB |
testcase_14 | AC | 23 ms
8,064 KB |
testcase_15 | AC | 4 ms
5,376 KB |
testcase_16 | AC | 5 ms
5,376 KB |
testcase_17 | AC | 5 ms
5,376 KB |
testcase_18 | AC | 3 ms
5,376 KB |
testcase_19 | AC | 13 ms
6,656 KB |
testcase_20 | AC | 17 ms
7,168 KB |
testcase_21 | AC | 7 ms
5,888 KB |
testcase_22 | AC | 6 ms
5,760 KB |
testcase_23 | AC | 4 ms
5,376 KB |
testcase_24 | AC | 19 ms
7,552 KB |
testcase_25 | AC | 6 ms
5,376 KB |
コンパイルメッセージ
main.cpp:57:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type] 57 | main(){ | ^~~~
ソースコード
#include <bits/stdc++.h> #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define FORR(i,a,b) for (int i=(a);i>=(b);i--) #define pb push_back #define pcnt __builtin_popcount #define show(x) cout<<#x<<" = "<<x<<endl; #define maxs(x,y) x = max(x,y) #define mins(x,y) x = min(x,y) #define fi first #define se second #define rng(a) a.begin(),a.end() #define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++) #define sz(x) (int)(x).size() using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vpii; typedef set<int> si; typedef pair<ll,ll> pll; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<pll> vpll; typedef set<ll> sl; template<typename T>string join(vector<T>&v) {stringstream s;FOR(i,0,sz(v))s<<' '<<v[i];return s.str().substr(1);} ll gcd(ll a,ll b){if(a>b)swap(a,b);for(;a>0;b%=a,swap(a,b));return b;} int modpow(ll a,ll n,int m){if(a==0)return a;ll p=1;for(;n>0;n/=2,a=a*a%m)if(n&1)p=p*a%m;return(int)p;} void dout(double d){printf("%.12f\n",d);} const int iinf = 1e9; const ll linf = 1e18; const int mod = 1e9+7; const double eps = 1e-10; struct Dijk{ // solve(s, g) or solve(s). // show d and p. typedef pair<ll,int> pli; int n; vector<vpll>E; vl d; vi p; void init(const vector<vpll>&e){n=sz(e);E=e;FOR(i,0,n)sort(rng(E[i]));d.resize(n);p.resize(n);} void o(int S,int G){FOR(i,0,n){d[i]=(i==S)?0:linf;p[i]=-1;}priority_queue<pli,vector<pli>,greater<pli>>Q;Q.push(pll(0,S));pli t;vector<bool>F;FOR(i,0,n)F.pb(0);ll f;int c=0,s;while(!Q.empty()){t=Q.top();Q.pop();f=t.fi;s=t.se;if(F[s])continue;F[s]=1;c++;if(c==n||s==G)break;each(itr,E[s]){ll ff=itr->fi,ss=itr->se;if((!F[ff])&&(f+ss<d[ff])){d[ff]=f+ss;p[ff]=s;Q.push(pll(f+ss,ff));}}}} ll solve(int s,int g){o(s,g);return d[g];} void solve(int s){o(s,-1);} }; ll n, v, s, g, L[100][100], d; vector<vpll> E; int pt[10000], tn, vn; set<pii> ss[10000]; main(){ cin.tie(0); ios::sync_with_stdio(false); cin >> n >> v; cin >> s >> d; s = (d - 1) * 100 + s - 1; cin >> g >> d; g = (d - 1) * 100 + g - 1; FOR(j, 0, n)FOR(i, 0, n)cin >> L[i][j]; E.resize(10000); FOR(i, 0, n)FOR(j, 0, n){ ll _i, _j; if(i > 0){ _i = i-1; _j = j; E[j*100+i].pb(pll(_j*100+_i, L[_i][_j])); } if(i < n-1){ _i = i+1; _j = j; E[j*100+i].pb(pll(_j*100+_i, L[_i][_j])); } if(j > 0){ _i = i; _j = j-1; E[j*100+i].pb(pll(_j*100+_i, L[_i][_j])); } if(j < n-1){ _i = i; _j = j+1; E[j*100+i].pb(pll(_j*100+_i, L[_i][_j])); } } Dijk dij; dij.init(E); d = dij.solve(s, g); if(d >= v){ cout << -1 << endl; return 0; } int mt = 0, co = g; while(dij.p[co] != -1){ co = dij.p[co]; mt++; } FOR(i, 0, 10000){ pt[i] = iinf; } typedef pair<pii, int> tii; priority_queue<tii, vector<tii>, greater<tii> > que; que.push(tii(pii(0, 0), s)); pt[s] = 0; ss[s].insert(pii(0,0)); tii t; while(true){ t = que.top(); que.pop(); if(t.se == g){ cout << t.fi.fi << endl; return 0; } each(itr, E[t.se]){ tn = t.fi.fi + 1; vn = t.fi.se + itr->se; if((vn < v)&&(pt[itr->fi]>vn)&&ss[itr->fi].find(pii(tn, vn))==ss[itr->fi].end()){ mins(pt[itr->fi], vn); ss[itr->fi].insert(pii(tn, vn)); que.push(tii(pii(tn, vn), itr->fi)); } } } }