Submission #537811

#TimeUsernameProblemLanguageResultExecution timeMemory
537811truc12a2cvpSoccer (JOI17_soccer)C++14
0 / 100
247 ms32556 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> II; const int N = 5e2 + 5, logN = 20; const int MOD = 1e9 + 7; const ll INF = 1e18; int h, w, a, b, c, dirs[5] = {0, 1, 0, -1, 0}, n, s[N], t[N]; ll dist[N][N][5], near[N][N]; inline bool inside(int x, int y){ return x >= 0 && x <= h && y >= 0 && y <= w; } void multiBFS(){ for(int i = 0; i <= h; i ++){ for(int j = 0; j <= w; j ++) near[i][j] = -1; } queue<II> qu; for(int i = 1; i <= n; i ++) near[s[i]][t[i]] = 0, qu.push(II(s[i], t[i])); while(!qu.empty()){ int x = qu.front().first, y = qu.front().second; qu.pop(); for(int i = 0; i < 4; i ++){ int nx = x + dirs[i], ny = y + dirs[i + 1]; if(inside(nx, ny) && near[nx][ny] == -1){ near[nx][ny] = near[x][y] + c; qu.push(II(nx, ny)); } } } } struct pack{ ll du; int x, y, lab; pack(ll _du = 0, int _x = 0, int _y = 0, int _lab = 0) : du(_du), x(_x), y(_y), lab(_lab) {} bool operator > (const pack& op) const{ return du > op.du; } }; void Dijkstra(){ for(int i = 0; i <= h; i ++) for(int j = 0; j <= w; j ++) for(int k = 0; k < 5; k ++) dist[i][j][k] = INF; dist[s[1]][t[1]][4] = 0; priority_queue<pack, vector<pack>, greater<pack>> pq; pq.push(pack(0, s[1], t[1], 4)); while(!pq.empty()){ ll du = pq.top().du; int x = pq.top().x, y = pq.top().y, lab = pq.top().lab; pq.pop(); if(du != dist[x][y][lab]) continue; if(lab != 4){ int nx = x + dirs[lab], ny = y + dirs[lab + 1]; if(dist[nx][ny][lab] > du + a){ dist[nx][ny][lab] = du + a; pq.push(pack(du + a, nx, ny, lab)); } if(dist[x][y][4] > du + near[x][y]){ dist[x][y][4] = du + near[x][y]; pq.push(pack(dist[x][y][4], x, y, 4)); } } else{ for(int i = 0; i < 4; i ++){ int nx = x + dirs[i], ny = y + dirs[i + 1]; if(dist[nx][ny][4] > du + c){ dist[nx][ny][4] = du + c; pq.push(pack(du + c, nx, ny, 4)); } if(dist[nx][ny][i] > du + a + b){ dist[nx][ny][i] = du + a + b; pq.push(pack(du + a + b, nx, ny, i)); } } } } cout << dist[s[n]][t[n]][4]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> h >> w >> a >> b >> c >> n; for(int i = 1; i <= n; i ++) cin >> s[i] >> t[i]; multiBFS(); Dijkstra(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...