[프로그래머스][C++][다익스트라] 합승 택시 요금

문제

프로그래머스

풀이

다익스트라

• 무지와 어피치가 S에서 경유지 I까지 같이 이동한다. 
• 무지와 어피치가 따로 A, B로 이동한다. 한명은 I에서 A로, 한명은 I에서 B로 이동한다.
• 즉, 최소 거리는 S -> I, I -> A, I -> B, 세 경로의 합의 최솟값이다. 
• S, A, B 세 노드에서 다른 노드로의 최소 거리만 있으면 문제를 풀 수 있다.
  • 현재 그래프는 양방향 경로이기 때문에, 다익스트라는 S, A, B 총 세 번만 실시해도 문제를 풀 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>

using namespace std;

vector<vector<int>> dist;
vector<vector<pair<int, int>>> edges;

void dijkstra(int start)
{
	dist[start][start] = 0;

	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));

	while (pq.empty() == false)
	{
		pair<int, int> current = pq.top();
		pq.pop();

		int currentNode = current.second;
		int currentDist = current.first * (-1);

		if (dist[start][currentNode] < currentDist)
		{
			continue;
		}

		for (auto edge : edges[currentNode])
		{
			int nextNode = edge.first;
			int nextDist = currentDist + edge.second;

			if (dist[start][nextNode] > nextDist)
			{
				dist[start][nextNode] = nextDist;

				pq.push(make_pair((-1) * nextDist, nextNode));
			}
		}
	}
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares)
{
	dist.resize(n + 1);
	for (int i = 1; i <= n; ++i)
	{
		dist[i].resize(n + 1, INT_MAX);
	}

	edges.resize(n + 1);
	for (int i = 0; i < fares.size(); ++i)
	{
		int firstNode = fares[i][0];
		int secondNode = fares[i][1];
		int dist = fares[i][2];

		edges[firstNode].push_back(make_pair(secondNode, dist));
		edges[secondNode].push_back(make_pair(firstNode, dist));
	}

	// 다익스트라는 s, a, b 세번만 실행
	dijkstra(s);
	dijkstra(a);
	dijkstra(b);

	// s -> i, i -> a, i -> b
	// 세 경로의 합의 최솟값
	int mini = INT_MAX;
	for (int i = 1; i <= n; ++i)
	{
		int currentDist = dist[s][i] + dist[a][i] + dist[b][i];

		mini = min(mini, currentDist);
	}

	return mini;
}

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

	vector<vector<int>> fares = {
		{4, 1, 10},
		{3, 5, 24},
		{5, 6, 2},
		{3, 1, 41},
		{5, 1, 24},
		{4, 6, 50},
		{2, 4, 66},
		{2, 3, 22},
		{1, 6, 25}
	};

	cout << solution(6, 4, 6, 2, fares);

	return 0;
}