Submission #398741

#TimeUsernameProblemLanguageResultExecution timeMemory
398741dualitySoccer (JOI17_soccer)C++11
100 / 100
577 ms21552 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- int dx[4] = {-1,0,1,0},dy[4] = {0,-1,0,1}; int S[100000],T[100000]; int dist[501][501]; queue<pii> Q; LLI dist2[501][501][6]; priority_queue<pair<LLI,pair<pii,int> > > HH; int main() { int i; int H,W,A,B,C,N; scanf("%d %d %d %d %d %d",&H,&W,&A,&B,&C,&N); for (i = 0; i < N; i++) scanf("%d %d",&S[i],&T[i]); int j,k; for (i = 0; i <= H; i++) { for (j = 0; j <= W; j++) dist[i][j] = -1; } for (i = 0; i < N; i++) { dist[S[i]][T[i]] = 0; Q.push(mp(S[i],T[i])); } while (!Q.empty()) { int y = Q.front().first; int x = Q.front().second; Q.pop(); for (i = 0; i < 4; i++) { int xx = x+dx[i],yy = y+dy[i]; if ((xx >= 0) && (xx <= W) && (yy >= 0) && (yy <= H) && (dist[yy][xx] == -1)) { dist[yy][xx] = dist[y][x]+1; Q.push(mp(yy,xx)); } } } for (i = 0; i <= H; i++) { for (j = 0; j <= W; j++) { for (k = 0; k < 6; k++) dist2[i][j][k] = -1; } } dist2[S[0]][T[0]][1] = 0,HH.push(mp(0,mp(mp(S[0],T[0]),1))); while (!HH.empty()) { LLI d = -HH.top().first; int y = HH.top().second.first.first; int x = HH.top().second.first.second; int s = HH.top().second.second; HH.pop(); if (d > dist2[y][x][s]) continue; if (s == 0) { if ((dist2[y][x][1] == -1) || (d+(LLI) C*dist[y][x] < dist2[y][x][1])) { dist2[y][x][1] = d+(LLI) C*dist[y][x]; HH.push(mp(-dist2[y][x][1],mp(mp(y,x),1))); } } else if (s == 1) { for (i = 0; i < 4; i++) { int xx = x+dx[i],yy = y+dy[i]; if ((xx >= 0) && (xx <= W) && (yy >= 0) && (yy <= H)) { if ((dist2[yy][xx][1] == -1) || (d+C < dist2[yy][xx][1])) { dist2[yy][xx][1] = d+C; HH.push(mp(-dist2[yy][xx][1],mp(mp(yy,xx),1))); } } if ((dist2[y][x][i+2] == -1) || (d+B < dist2[y][x][i+2])) { dist2[y][x][i+2] = d+B; HH.push(mp(-dist2[y][x][i+2],mp(mp(y,x),i+2))); } } } else { if ((dist2[y][x][0] == -1) || (d < dist2[y][x][0])) { dist2[y][x][0] = d; HH.push(mp(-dist2[y][x][0],mp(mp(y,x),0))); } int xx = x+dx[s-2],yy = y+dy[s-2]; if ((xx >= 0) && (xx <= W) && (yy >= 0) && (yy <= H)) { if ((dist2[yy][xx][s] == -1) || (d+A < dist2[yy][xx][s])) { dist2[yy][xx][s] = d+A; HH.push(mp(-dist2[yy][xx][s],mp(mp(yy,xx),s))); } } } } printf("%lld\n",min(dist2[S[N-1]][T[N-1]][0],dist2[S[N-1]][T[N-1]][1])); return 0; }

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d %d %d %d %d %d",&H,&W,&A,&B,&C,&N);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:68:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     for (i = 0; i < N; i++) scanf("%d %d",&S[i],&T[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...