글 읽기 - 4485. 질문있습니다.(코드)

minjae200 5년 전 0

map[i][j]을 기준으로 우선순위큐 다익스트라 BFS 썻는데 50프로에서 틀렸다고 나옵니다.

다른분들 코드랑 다른점도 못느꼇는데 어디가 틀린건가요..

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <functional>
using namespace std;

#define MAX_V 130
#define INF 987654321
typedef pair<int, pair<int, int>> pii;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int N;
bool checkRange(int y, int x)
{
	if (1 <= y && y <= N && 1 <= x && x <= N) return true;
	else return false;
}

int main(void)
{
	int qcnt = 0;
	while (1) {
		cin >> N;
		if (N == 0) break;
		qcnt++;
		int map[MAX_V][MAX_V];
		int dp[MAX_V][MAX_V];
		priority_queue<pii, vector<pii>, greater<pii>> pq;

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				cin >> map[i][j];
				dp[i][j] = INF;
			}
		}
		pq.push(make_pair(map[1][1], make_pair(1, 1)));
		dp[1][1] = map[1][1];

		while (!pq.empty()) {
			int cur_y = pq.top().second.first;
			int cur_x = pq.top().second.second;
			pq.pop();

			for (int i = 0; i < 4; i++) {
				int next_y = cur_y + dy[i];
				int next_x = cur_x + dx[i];
				if (!checkRange(next_y, next_x)) continue;
				if (dp[next_y][next_x] > dp[cur_y][cur_x] + map[next_y][next_x]) {
					dp[next_y][next_x] = dp[cur_y][cur_x] + map[next_y][next_x];
					pq.push(make_pair(dp[next_y][next_x],make_pair(next_y, next_x)));
				}
			}
		}

		printf("Question %d: %d\n", qcnt, dp[N][N]);
	}
	return 0;
}

djm03178 5년 전 1

Question이 아니고 Problem입니다.

minjae200 5년 전 0

@djm03178

흑...고쳐도안되네요

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

문제

문제

출처

ICPC

4485. 질문있습니다.(코드)

minjae200 5년 전 0

djm03178 5년 전 1

minjae200 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말