Level 3. 합승 택시 요금

Level 3. 합승 택시 요금

 

 

플로이드-워셜 알고리즘을 응용하는 문제다.

• 모든 점들 간의 최단 거리를 구해야 할 때 사용한다.
• 3중 for문을 이용하는 O(n³) 시간 복잡도 때문에, 정점의 개수가 200개 미만으로 적은 것이 특징이다.
• 초기화 시 ∞를 무조건 INT_MAX로 설정하면, 더할 때 음수가 돼버리므로 주의해야 한다.

 

우선 모든 점들 간의 최단 거리를 구한 후, (S → I 비용) + (I → A 비용) + (I → B 비용)이 S에서 I까지 합승 후 각자 집으로 간 비용이다.

• 이 값들의 최솟값을 구하면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

#define UNREACHABLE 19'900'000

using namespace std;

int solution(int n, int s, int a, int b, vector<vector<int>> fares)
{
    int answer = UNREACHABLE;
    vector<vector<int>> graph(n + 1, vector<int>(n + 1, UNREACHABLE));

    for (int i = 1; i <= n; ++i)  graph[i][i] = 0;
    for (vector<int>& fr : fares) graph[fr[0]][fr[1]] = graph[fr[1]][fr[0]] = fr[2];

    for (int K = 1; K <= n; ++K)
        for (int S = 1; S <= n; ++S)
            for (int E = 1; E <= n; ++E)
                graph[S][E] = min(graph[S][E], graph[S][K] + graph[K][E]);

    for (int i = 1; i <= n; ++i)
        answer = min(answer, graph[s][i] + graph[i][a] + graph[i][b]);

    return answer;
}