Submission #527892

#TimeUsernameProblemLanguageResultExecution timeMemory
527892AdamGSSoccer (JOI17_soccer)C++17
100 / 100
767 ms39192 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back const int LIM=507, MAXN=1e5+7; const ll INF=1e18+7; int dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1}; ll wart[LIM][LIM], odl[LIM][LIM][5], h, w, a, b, c, n; pair<int,int>T[MAXN]; bool ok(int a, int b) { return 0<=a && a<h && 0<=b && b<w; } void BFS() { rep(i, h) rep(j, w) wart[i][j]=INF; queue<pair<int,int>>q; rep(i, n) { wart[T[i].st][T[i].nd]=0; q.push({T[i].st, T[i].nd}); } while(!q.empty()) { int x=q.front().st, y=q.front().nd; q.pop(); rep(i, 4) if(ok(x+dx[i], y+dy[i]) && wart[x+dx[i]][y+dy[i]]==INF) { wart[x+dx[i]][y+dy[i]]=wart[x][y]+c; q.push({x+dx[i], y+dy[i]}); } } } void dijkstra() { rep(i, h) rep(j, w) rep(l, 5) odl[i][j][l]=INF; priority_queue<pair<ll,pair<pair<int,int>,int>>>q; q.push({0, {{T[0].st, T[0].nd}, 0}}); while(!q.empty()) { ll o=-q.top().st, x=q.top().nd.st.st, y=q.top().nd.st.nd, l=q.top().nd.nd; q.pop(); if(odl[x][y][l]<=o) continue; odl[x][y][l]=o; if(!l) { rep(i, 4) if(ok(x+dx[i], y+dy[i])) { if(odl[x+dx[i]][y+dy[i]][0]>o+c) q.push({-o-c, {{x+dx[i], y+dy[i]}, 0}}); if(odl[x+dx[i]][y+dy[i]][i+1]>o+a+b) q.push({-o-a-b, {{x+dx[i], y+dy[i]}, i+1}}); } continue; } if(odl[x][y][0]>o+wart[x][y]) q.push({-o-wart[x][y], {{x, y}, 0}}); if(ok(x+dx[l-1], y+dy[l-1]) && odl[x+dx[l-1]][y+dy[l-1]][l]>o+a) q.push({-o-a, {{x+dx[l-1], y+dy[l-1]}, l}}); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> h >> w >> a >> b >> c >> n; ++h; ++w; rep(i, n) cin >> T[i].st >> T[i].nd; BFS(); dijkstra(); ll ans=INF; rep(i, 5) ans=min(ans, odl[T[n-1].st][T[n-1].nd][i]); cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...