[BOJ] 월요병

[BOJ] 월요병

Problem URL : 월요병

#include <iostream>
#include <queue>
#include <vector>
#define ll long long
#define INF 1e9 * 90001 // 최대 10억 * 300 * 300
using namespace std;
int dx[] = { 0,0,1,-1,1,1,-1,-1 };
int dy[] = { 1,-1,0,0,1,-1,1,-1 };
int n, m;
int arr[301][301];
ll dist[301][301];
// 위, 오른쪽 변에서 출발하여 아래, 왼쪽 변에 도달하는 경로들 중 최솟값을 찾는다
ll dijkstra() {
	priority_queue< pair<ll, pair<int, int>>, vector< pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>> > pq;
	for (int i = 0; i < m; i++) {
		if (arr[0][i] == -1) {
			continue;
		}
		pq.push({ arr[0][i],{ 0,i } });
		dist[0][i] = arr[0][i];
	}
	for (int i = 0; i < n; i++) {
		if (arr[i][m - 1] == -1) {
			continue;
		}
		pq.push({ arr[i][m - 1],{ i,m - 1 } });
		dist[i][m - 1] = arr[i][m - 1];
	}
	while (!pq.empty()) {
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		ll cost = pq.top().first;
		pq.pop();
		if (cost > dist[x][y]) {
			continue;
		}
		for (int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m || arr[nx][ny] == -1) {
				continue;
			}
			ll nCost = cost + arr[nx][ny];
			if (nCost < dist[nx][ny]) {
				pq.push({ nCost, {nx, ny} });
				dist[nx][ny] = nCost;
			}
		}
	}
	ll ret = INF;
	for (int i = 0; i < n; i++) {
		ret = min(dist[i][0], ret);
	}
	for (int i = 0; i < m; i++) {
		ret = min(dist[n - 1][i], ret);
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == -2) {
				arr[i][j] = 0;
			}
			dist[i][j] = INF;
		}
	}
	ll ans = dijkstra();
	if (ans == INF) {
		ans = -1;
	}
	cout << ans;
	return 0;
}

Comments

INF 값을 충분히 크게 잡아주지 않으면 틀린다. (주의하자!)