[백준/BOJ] 백준 17940번 : 지하철

https://www.acmicpc.net/problem/17940

17940번: 지하철

환승 횟수가 작은 게 먼저 나오고, 환승 횟수가 같다면 최소 비용이 먼저 나오는 우선순위 큐를 이용하여 다익스트라 알고리즘을 활용해서 문제를 해결했다.

 

코드

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

int n, m;
vector<int> company(1000, 0);
vector<pair<int, int>> adj[1000];

pair<int, int> Solve(int start)
{
	vector<int> short_change(1000, 987654321); //[위치] = 최소 환승 횟수
	vector<int> short_cost(1000, 987654321); //[위치] = 해당위치의 최소 환승횟수에서 최단 경로

	short_change[start] = 0;
	short_cost[start] = 0;

	priority_queue<tuple<int, int, int>> pq;
	pq.push(make_tuple(-0, -0, start)); //(-최소 환승 횟수, -최소 비용, 위치)

	while (!pq.empty())
	{
		int here_turn = -get<0>(pq.top());
		int here_cost = -get<1>(pq.top());
		int here = get<2>(pq.top());
		pq.pop();

		if (here_turn > short_change[here])
			continue;
		if (here_cost > short_cost[here])
			continue;

		//목적지에 도착 했을때
		if (here == m)
			break;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there_turn = here_turn;
			int there_cost = here_cost + adj[here][i].first;
			int there = adj[here][i].second;

			if (company[here] != company[there])
				there_turn++;

			//더 짧은 환승을 찾았을때
			if (short_change[there] > there_turn)
			{
				short_change[there] = there_turn;
				short_cost[there] = there_cost;
				pq.push(make_tuple(-there_turn, -there_cost, there));
			}

			//같은 환승 횟수지만 더 작은 비용을 찾았을때
			else if (short_change[there] == there_turn && short_cost[there] > there_cost)
			{
				short_cost[there] = there_cost;
				pq.push(make_tuple(-there_turn, -there_cost, there));
			}
		}
	}

	return make_pair(short_change[m], short_cost[m]);
}

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

	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		int c;
		cin >> c;
		company[i] = c;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int input;
			cin >> input;

			if (input == 0)
				continue;

			adj[i].push_back(make_pair(input, j));
		}
	}

	pair<int, int> result = Solve(0);

	cout << result.first << " " << result.second << "\n";

	return 0;
}