글 읽기 - 반례가 있는지 , 논리의 예외케이스가 존재하는지 궁금합니다.

nakgee 4년 전 0

각 Line의 1번과 C번을 vertex로하는 그래프의 모든 최단경로를 n^2에 찾아야 한다고 생각했습니다.

그래서 최단경로를 구해주고

조건에 맞게 처리 해주었는데 7%에서 WA가 뜨네요... 도와주십쇼...!

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

#define N 220
#define RCMAX 400010
#define INF 111111111
typedef pair<int, int> pii;


int R, C;
int map[N * 10][N];// 200*2000 400000
long long goL[N * 10][N], goR[N * 10][N];
int sum[N];

long long dis[N * 20][N * 20];


void makepath() {
	for (int i = 1; i <= R; i++) {
		int l = i * 2 - 2;
		int r = i * 2 - 1;
		dis[l][l] = map[i][1];
		dis[r][r] = map[i][C];

		int res = sum[i];

		int now = map[i][1] + map[i][C];
		for (int j = i + 1; j <= R; j++) {
			res = min(now + sum[j], res);
			now += map[j][1] + map[j][C];
		}
		now = map[i][1] + map[i][C];
		for (int j = i - 1; j >= 1; j--) {
			res = min(now + sum[j], res);
			now += map[j][1] + map[j][C];
		}
		dis[l][r] = dis[r][l] = res;
	}

	for (int ix = 0; ix < 2 * R; ix += 2) {
		for (int iy = 0; iy <= 1; iy++) {
			for (int jx = ix + 2; jx < 2*R; jx+=2) {
				for (int jy = 0; jy <= 1; jy++) {
					int x = ix + iy;
					int y = jx + jy;
					dis[x][y] = dis[y][x] =	min(dis[x][jx - 2] + dis[jx][y], dis[x][jx - 1] + dis[jx + 1][y]);
				}
			}
		}
	}


}
long long getdis(int sx, int sy, int ex, int ey) {
	

	
	long long Left = goL[sx][sy] - map[sx][1];
	Left += min(dis[2 * sx - 2][2 * ex - 2] + goL[ex][ey] - map[ex][1], dis[2 * sx - 2][2 * ex - 1] + goR[ex][ey]- map[ex][C]);

	long long Right = goR[sx][sy] - map[sx][C];
	Right += min(dis[2 * sx - 1][2 * ex - 2] + goL[ex][ey] - map[ex][1], dis[2 * sx - 1][2 * ex - 1] + goR[ex][ey] - map[ex][C]);

	long long ret =min(Left, Right);

	if (sx == ex) {
		if (ey >= sy) ret = min(ret, goL[sx][ey] - goL[sx][sy - 1]);
		else ret = min(ret, goL[sx][sy] - goL[sx][ey - 1]);
	}

	return ret;
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			cin >> map[i][j];
			sum[i] += map[i][j];
		}
	}
	for (int i = 1; i <= R; i++) {
		int now = 0;
		for (int j = 1; j <= C; j++) {
			now += map[i][j];
		    goL[i][j] = now;
			goR[i][j] = sum[i] - now + map[i][j];
		}
	}
	makepath();

	int D;
	cin >> D;
	int tx ,ty,sx = 1,sy = 1;
	long long res = map[1][1];
	
	while (D--) {
		cin >> tx >> ty;

		res += getdis(sx, sy, tx, ty) - map[sx][sy];
		sx = tx;
		sy = ty;
	}
	cout << res;
	return 0;
}

WeissBlume 4년 전 1

> 각 Line의 1번과 C번을 vertex로하는 그래프의 모든 최단경로를 n^2에 찾아야 한다고 생각했습니다.

아이디어는 맞습니다. 구현에 실수가 있을 것으로 보이네요.

nakgee 4년 전 0

답변 감사합니다
처음에 다익스트라를 통해 접근을 했다가 모든 최단경로 구하기가 힘들어 dp를 이용해서 구현했는데

이 방법의 예외가 있을 수도 있을까라는 생각이 들었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례가 있는지 , 논리의 예외케이스가 존재하는지 궁금합니다.

nakgee 4년 전 0

WeissBlume 4년 전 1

nakgee 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말