Submission #20963

#	Time	Username	Problem	Language	Result	Execution time	Memory
20963		kdh9949	Soccer (JOI17_soccer)	C++14	100 / 100	1573 ms	87888 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Bfs{
	int x, y;
};

struct Dijk{
	int x, y, d; ll md;
	bool operator<(const Dijk &oth) const {
		return md > oth.md;
	}
};

int n, m, k, sx, sy, ex, ey;
ll A, B, C, c[505][505], md[505][505][5];
queue<Bfs> q;
priority_queue<Dijk> pq;

const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
const ll inf = 1e18;

int val(int x, int y){ return x >= 1 && x <= n && y >= 1 && y <= m; }

int main(){
	scanf("%d%d%lld%lld%lld%d", &n, &m, &A, &B, &C, &k); n++; m++;
	for(int i = 1; i <= n; i++) fill(c[i] + 1, c[i] + m + 1, inf);
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) fill(md[i][j], md[i][j] + 5, inf);
	for(int i = 1; i <= k; i++){
		int x, y; scanf("%d%d", &x, &y); x++; y++;
		c[x][y] = 0; q.push({x, y});
		if(i == 1){
			sx = x; sy = y;
			md[sx][sy][4] = 0;
			pq.push({sx, sy, 4, 0});
		}
		else if(i == k){ ex = x; ey = y; }
	}
	while(!q.empty()){
		Bfs cur = q.front(); q.pop();
		for(int i = 0; i < 4; i++){
			int nx = cur.x + dx[i], ny = cur.y + dy[i];
			if(!val(nx, ny)) continue;
			ll nd = c[cur.x][cur.y] + C;
			if(c[nx][ny] > nd){
				c[nx][ny] = nd;
				q.push({nx, ny});
			}
		}
	}
	while(!pq.empty()){
		Dijk cur = pq.top(); pq.pop();
		ll w = cur.d == 4 ? 0 : c[cur.x][cur.y];
		for(int i = 0; i < 4; i++){
			int nx = cur.x + dx[i], ny = cur.y + dy[i];
			ll nd = cur.md + w + C;
			if(val(nx, ny) && md[nx][ny][4] > nd){
				md[nx][ny][4] = nd;
				pq.push({nx, ny, 4, nd});
			}
			nd = cur.md + (cur.d == i ? 0 : w + B) + A;
			if(val(nx, ny) && md[nx][ny][i] > nd){
				md[nx][ny][i] = nd;
				pq.push({nx, ny, i, nd});
			}
		}
	}
	printf("%lld", *min_element(md[ex][ey], md[ex][ey] + 5));
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:27:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld%lld%lld%d", &n, &m, &A, &B, &C, &k); n++; m++;
                                                     ^
soccer.cpp:31:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y); x++; y++;
                                  ^

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65