[백준/BOJ] 백준 20046번 : Road Reconstruction

www.acmicpc.net/problem/20046

20046번: Road Reconstruction

다익스트라 알고리즘을 이용하여 start에서 dest까지 가는 경로를 만드는데 드는 최소 비용을 구한다. start가 도로를 건설할 수 없는 위치일 때는 start에서 dest까지 가는 경로를 만들 수 없다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

int m, n;
int board[1000][1000];
int dxdy[4][2] = { {0,-1},{-1,0},{0,1},{1,0} };

//다익스트라 알고리즘을 이용하여 start에서 dest까지 가는 경로를 만드는데 드는 최소 비용을 구한다
int Solve(pair<int, int> start, pair<int, int> dest)
{
	//시작위치가 도로를 건설할 수 없는 위치일때
	if (board[start.first][start.second] == -1)
		return -1;

	vector<vector<int>> result(m, vector<int>(n, 987654321));
	priority_queue<pair<int, pair<int, int>>> pq;

	result[start.first][start.second] = board[start.first][start.second];
	pq.push(make_pair(-result[start.first][start.second], make_pair(start.first, start.second)));

	while (!pq.empty())
	{
		pair<int, int> here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dxdy[i][0], here.second + dxdy[i][1]);

			//there가 갈 수 있는 위치일때
			if (there.first >= 0 && there.first < m && there.second >= 0 && there.second < n && board[there.first][there.second] != -1)
			{
				int there_cost = here_cost + board[there.first][there.second];

				if (result[there.first][there.second] > there_cost)
				{
					result[there.first][there.second] = there_cost;
					pq.push(make_pair(-there_cost, there));
				}
			}
		}
	}

	if (result[dest.first][dest.second] == 987654321)
		return -1;

	else
		return result[dest.first][dest.second];
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input;

	cin >> m >> n;

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> input;
			board[i][j] = input;
		}
	}

	cout << Solve(make_pair(0, 0), make_pair(m - 1, n - 1));

	return 0;
}