제출 #1199453

#제출 시각아이디문제언어결과실행 시간메모리
1199453Saul0906Soccer (JOI17_soccer)C++20
35 / 100
1457 ms34448 KiB
#include <bits/stdc++.h> #define fi first #define se second #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define rep(a,b,c) for(ll a=b; a<c; a++) #define repr(a,b,c) for(ll a=b-1; a>c-1; a--) #define repa(a,b) for(auto a:b) #define mid ((l+r)>>1) #define endl "\n" #define pq_min(a) priority_queue<a,vector<a>,greater<a>> #define lll array<ll,3> #define pb push_back #define ppb pop_back #define int ll using namespace std; using vi = vector<int>; const ll inf=1e18; const int mov[4][2]{ {1,0}, {0,1}, {-1,0}, {0,-1} }; inline ll abss(ll a){ if(a>=0) return a; return -a; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll h, w, a, b, c, n; cin>>h>>w>>a>>b>>c>>n; h++; w++; int s[n], t[n]; ll dis[h+2][w+2], vis[h+2][w+2]{}, cr[h+1][w+1], cc[h+1][w+1]; rep(i,0,n){ cin>>s[i]>>t[i]; s[i]++; t[i]++; vis[s[i]][t[i]]=true; } rep(i,1,h+1) rep(j,1,w+1) cc[i][j]=cr[i][j]=inf; rep(i,1,h+1){ ll mn=inf; rep(j,1,w+1){ if(vis[i][j]) mn=0; cc[i][j]=min(cc[i][j],mn); mn++; } mn=inf; repr(j,w+1,1){ if(vis[i][j]) mn=0; cc[i][j]=min(cc[i][j],mn); mn++; } } rep(j,1,w+1){ ll mn=inf; rep(i,1,h+1){ if(vis[i][j]) mn=0; cr[i][j]=min(cr[i][j],mn); mn++; } mn=inf; repr(i,h+1,1){ if(vis[i][j]) mn=0; cr[i][j]=min(cr[i][j],mn); mn++; } } rep(i,0,h+2) rep(j,0,w+2) vis[i][j]=1; rep(i,1,h+1) rep(j,1,w+1) vis[i][j]=0; rep(i,0,h+2) rep(j,0,w+2) dis[i][j]=inf; pq_min(lll) pq; pq.push({0,s[0],t[0]}); dis[s[0]][t[0]]=0; while(pq.size()){ ll x=pq.top()[1], y=pq.top()[2], W=pq.top()[0], z; pq.pop(); if(vis[x][y]) continue; vis[x][y]=true; rep(i,0,4){ x+=mov[i][0]; y+=mov[i][1]; if(!vis[x][y] && dis[x][y]>W+c){ dis[x][y]=W+c; pq.push({dis[x][y],x,y}); } x-=mov[i][0]; y-=mov[i][1]; } if(a<c){ rep(i,1,h+1){ if(cc[i][y]<=h*w) z=min(inf,W+a*abss(x-i)+b+c*cc[i][y]); else z=inf; if(!vis[i][y] && dis[i][y]>z){ dis[i][y]=z; pq.push({z,i,y}); } } rep(i,1,w+1){ if(cr[x][i]<=h*w) z=min(inf,W+a*abss(y-i)+b+c*cr[x][i]); else z=inf; if(!vis[x][i] && dis[x][i]>z){ dis[x][i]=z; pq.push({z,x,i}); } } } } cout<<dis[s[n-1]][t[n-1]]<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...