[백준][C++] 4485: 녹색 옷 입은 애가 젤다지?

문제 링크: https://www.acmicpc.net/problem/4485

 

최단경로 문제입니다. 다익스트라 알고리즘을 써서 풀면 간단합니다. 음수간선이 없으니 음수사이클도 없습니다.

2차원 배열 형태 그래프를 적절히 써주면 됩니다

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

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


const int INF = 987654321;
const int MAX_V = 125;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };

int n;
vector<vector<int>> adj;
vector<vector<int>> dist;


inline bool in_range(int y, int x) {
	return y >= 0 && y < n && x >= 0 && x < n;
}

int dijkstra_2d() {
	priority_queue<tuple<int, int, int>> pq;	// cost(-), y, x
	pq.emplace(-adj[0][0], 0, 0);
	dist[0][0] = adj[0][0];

	while (!pq.empty()) {
		auto [cost, y, x] = pq.top();
		pq.pop();
		cost = -cost;

		if (dist[y][x] < cost) continue;

		for (int i = 0; i < 4; ++i) {
			auto next_y = y + dy[i];
			auto next_x = x + dx[i];
			if (!in_range(next_y, next_x)) continue;

			auto nextDist = cost + adj[next_y][next_x];

			if (dist[next_y][next_x] > nextDist) {
				dist[next_y][next_x] = nextDist;
				pq.emplace(-nextDist, next_y, next_x);
			}
		}
	}

	return dist[n-1][n-1];
}


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	for (int test_case=1; ; ++test_case) {
		cin >> n;
		if (n == 0) break;

		//init
		adj = vector<vector<int>>(n, vector<int>(n));
		dist = vector<vector<int>>(n, vector<int>(n, INF));

		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				cin >> adj[i][j];

		cout << "Problem " << test_case << ": " << dijkstra_2d() << '\n';
	}
	
	return 0;
}