글 읽기 - 할로윈 묘지...

nochedeuyuni 4년 전 0

안녕하세요

다른 블로그를 참고하여 코드를 짰는데 (https://skyde47.tistory.com/56 )

아무리봐도 변수명 만 다르고 다 같은것 같은데

블로그의 코드는 "맞았습니다"가 뜨고

제가 참고해서 쓴 코드는 "틀렸습니다"라고 뜹니다...

문제에서 언급된 예시는 당연히 맞았구요,,,

뭐가 문제인지 알려주실수 있을까요..?

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 999999999;
struct mGo {
	int x1, y1, x2, y2, t, v; //v -1(묘지), 0(잔디), 1(귀신구멍)
	mGo(int sx, int sy, int x, int y, int t, int v) :x1(sx), y1(sy), x2(x), y2(y), t(t), v(v) {}
	mGo() {}
};
vector<mGo> edge;
mGo arr[31][31]; //(i,j)의 특성 v를 저장, 만약 귀신구멍이라면 x2,y2,t도 저장
int dp[31][31]; //(0,0)에서 (i,j)까지의 최단시간
int W, H, G, E, x11, y11, x22, y22, t;
bool status;
int dx[4] = {-1,0,1,0};
int dy[4] = { 0,1,0,-1 };

int main() {
	while (true) {
		scanf("%d %d", &W, &H);
		if (!W && !H)
			return 0;
		//초기화
		edge.clear();
		status = false;
		for (int i = 0; i < H; i++)
			for (int j = 0; j < W; j++)
				arr[i][j] = mGo(0, 0, 0, 0, 0,0);
		//묘비 입력
		scanf("%d", &G);
		for (int i = 0; i < G; i++) {
			scanf("%d %d", &x11, &y11);
			arr[y11][x11].v = -1;
		}
		//귀신구멍입력
		scanf("%d", &E);
		for (int i = 0; i < E; i++) {
			scanf("%d %d %d %d %d", &x11, &y11, &x22, &y22, &t);
			arr[y11][x11] = mGo(x11, y11, x22, y22, t, 1);
		}
		//간선 추가
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				dp[i][j] = INF;
				if (arr[i][j].v == -1) {//묘비 이동불가
					continue;
				}
				else if (arr[i][j].v == 0) {//잔디밭
					if (i == H - 1 && j == W - 1)
						continue;
					for (int k = 0; k < 4; k++) {//4방향
						int ny = i + dy[k];
						int nx = j + dx[k];
						if (ny < 0 || ny == H || nx == W || nx < 0 || arr[ny][nx].v == -1)
							continue;
						edge.push_back(mGo(j,i, nx, ny, 1, 0));
					}
				}
				else {//텔레포트
					edge.push_back(arr[i][j]);
				}
			}
		}
		//O(VE) 벨만포드
		dp[0][0] = 0;
		for (int i = 0; i < H*W; i++) {
			status = false;
			for (mGo ee : edge) {//모든 간선
				if (dp[ee.y2][ee.x2] > dp[ee.y1][ee.x1] + ee.t) {
					dp[ee.y2][ee.x2] = dp[ee.y1][ee.x1] + ee.t;
					status = true;
				}
			}
			//음의 사이클 확인
			if (i == W * H - 1) {
				if(status)printf("Never\n");
				else if (dp[H - 1][W - 1] == INF)
					printf("Impossible\n");
				else
					printf("%d\n", dp[H - 1][W - 1]);
			}
		}
	}
	return 0;
}

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

문제

문제

출처

ICPC

할로윈 묘지...

nochedeuyuni 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말