프로그래머스 : 합승 택시 요금

​https://programmers.co.kr/learn/courses/30/lessons/72413

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

 

​

다익스트라를 이용하여 풀었습니다.

특정한 i 지점에서 내린다고 했을 때,

(S -> i 까지의 최소 비용) + (i -> A 까지의 최소 비용) + (i -> B 까지의 최소 비용) 의 최솟값을 구해주었습니다.

S == i일 때가 합승을 하지 않는 상황입니다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 666666666
using namespace std;

vector<vector<pair<int, int>>> graph(201, vector<pair<int, int>>());

vector<int> dijkstra(int n, int start) {
    priority_queue<pair<int, int>> pq;
    vector<int> fare(n+1, INF);
    fare[start] = 0;
    pq.push({0, start});
    while(!pq.empty()) {
        int cost = -pq.top().first;
        int pos = pq.top().second;
        pq.pop();
        if(cost > fare[pos]) continue;
        for(int i=0; i<graph[pos].size(); i++) {
            int nextPos = graph[pos][i].first;
            int nextCost = cost + graph[pos][i].second;
            if(fare[nextPos] > nextCost) {
                fare[nextPos] = nextCost;
                pq.push({-nextCost, nextPos});
            }
        }
    }
    return fare;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int ans = INF;
    for(int i=0; i<fares.size(); i++) {
        int a = fares[i][0];
        int b = fares[i][1];
        int f = fares[i][2];
        graph[a].push_back({b, f});
        graph[b].push_back({a, f});
    }
    
    vector<int> sFare = dijkstra(n, s);
    vector<int> aFare = dijkstra(n, a);
    vector<int> bFare = dijkstra(n, b);
    for(int i=1; i<= n; i++)
        ans = min(ans, sFare[i] + aFare[i] + bFare[i]);
    return ans;
}