[프로그래머스 2021 KAKAO BLIND RECRUITMENT] 합승 택시 요금

문제

programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

 

풀이

1. N이 200이하로 작으므로 플로이드 와샬을 사용하여 $O(N^3)$내에 모든 정점간의 최단거리를 구할 수 있습니다. 

 

2. 모든 정점을 순회하며 보는 정점을 경유지로 삼으면 (출발 - >경유지) + (경유지 -> a) + (경유지 -> b)로가는 비용을  최소화한게 정답입니다. ( 세 경로에서 두 정점은 모두 연결되어 있어야 합니다.)

 

코드

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

const int inf = 0x3f3f3f3f;
int cost[201][201];

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
	int answer = inf;
	memset(cost, inf, sizeof(cost));
	for (int i = 1; i <= n; i++) cost[i][i] = 0;
	for (int i = 0; i < fares.size(); i++) {
		int u = fares[i][0], v = fares[i][1], w = fares[i][2];
		cost[u][v] = cost[v][u] = w;
	}
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (cost[i][j] > cost[i][k] + cost[k][j])
					cost[i][j] = cost[i][k] + cost[k][j];
	for (int cur = 1; cur <= n; cur++) {
		if (cost[s][cur] == inf || cost[cur][a] == inf || cost[cur][b] == inf) continue;
		answer = min(answer, cost[s][cur] + cost[cur][a] + cost[cur][b]);
	}
	return answer;
}