프로그래머스 - 합승 택시 요금(72413)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72413

---

문제 설명

A와 B는 택시를 타고 귀가하려고 합니다. 이때 A와 B는 가능한 택시요금이 적게나오는 루트로 합승하려고 합니다.

택시를 타고 갈 수 있는 n개의 지점 중 택시를 타는 s지점, A와 B의 집인 a, b지점, 각 지점간의 택시요금이 주어졌을 때, 최소 택시요금을 구하시오.

제한조건

* s, a, b 지점은 겹치지 않습니다. 또한 s지점에서 반드시 a, b 지점으로 갈 수 있는 경로만 주어집니다.

* n <= 200

---

아이디어

시작 지점 s에서 합승할 지점 k까지 간 후, k에서 각각 a, b지점으로 가는 최소 요금을 구하면 되니 각 지점 사이 최단거리를 미리 구해 놓고 위에 방법을 그대로 사용.

다른 방식으로는 시작지점에서 a, b를 도착지점으로하고 중간마다 경유를 할지 선택하는 방법은 더 귀찮을 것 같네요.

---

코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> table(201, vector<int>(201, 2e8));
int answer = 2e9;

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    for(auto fare : fares)
    {
        table[fare[0]][fare[1]] = fare[2];
        table[fare[1]][fare[0]] = fare[2];
    }

    for(int i = 0; i <= n; i++) table[i][i] = 0;

    for(int k = 0; k <= n; k++)
        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= n; j++)
                table[i][j] = min(table[i][j], table[i][k] + table[k][j]);
    
    for(int i = 0; i <= n; i++)
        answer = min(answer, (table[s][i] + table[i][a] + table[i][b]));
    
    return answer;
}

아이디어와 동일하게 임의의 두 지점 i > j로 갈 때 최단거리를 벨만포드 알고리즘으로 구하고,
시작지점 s에서 합승 지점 i 까지 간 후 a, b로 가는 것에 최소 값을 체크.

---