[c++/프로그래머스] 합승 택시 요금

문제 링크

합승 택시 요금

풀이

다익스트라로 푸는 문제. 시간 초과 날 것 같았는데 안나네 ..

1. 먼저 인접리스트를 초기화한다.
2. 시작 노드부터 다익스트라로 최단 거리를 계산한다.
   2-1. dijkstra 함수를 만들어 계산하였다. 모든 노드까지를 무한대로 두고 (나 같은 경우, 노드가 최대 200개, 요금은 최대 100,000이므로 20,000,000 이상은 안나올 것이라 생각해 정의해주었다) 우선 순위 큐를 이용해 최단 노드를 계속 갱신해준다.
3. 여기가 핵심 알고리즘인데, 2번까지 해서 최단 경로가 있는 벡터가 반환될 텐데, 바로 [a]와 [b]를 더해주면 처음부터 각자 가는 것이다.
   3-1. 노드를 다 돌면서 시작 노드부터 해당 노드까지는 같이 가고, 해당 노드부터 a와 b까지는 각자 가는 것으로 다시 dijkstra를 구해준다.
4. 모든 루트를 다 돌면서 제일 적은 금액이 최소 금액이 될 것이다.

코드

#include <string>
#include <vector>
#include <queue>
#define INF 20000000

using namespace std;

vector<int> dijkstra(vector<vector<pair<int,int>>> &adj, int s)
{
    vector<int> dist(adj.size(), INF);
    dist[s] = 0;
    
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0,s});
    while(!pq.empty())
    {
        int cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        for(int i=0;i<adj[cur].size();i++)
        {
            pair<int,int> node = adj[cur][i];
            if(cost+node.first < dist[node.second])
            {
                pq.push({node.first+cost, node.second});
                dist[node.second] = cost+node.first;
            }
        }
    }
    
    return dist;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    
    vector<vector<pair<int,int>>> adj(n+1); // 인접리스트
    for(int i=0;i<fares.size();i++) // 초기화
    {
        int stt = fares[i][0];
        int end = fares[i][1];
        int cost = fares[i][2];
        adj[stt].push_back({cost, end});
        adj[end].push_back({cost, stt});
    }
    
    vector<int> sttRoute = dijkstra(adj, s);
    answer = sttRoute[a] + sttRoute[b]; // 처음부터 각자 가는거
    for(int i=1;i<=n;i++)
    {
        if(i == s) continue;
        
        int tmp = sttRoute[i]; // i까지는 같이 가고
        
        vector<int> tmpArr = dijkstra(adj, i);
        tmp += tmpArr[a] + tmpArr[b]; // 각자 집 따로 가기
        
        answer = min(answer, tmp);
    }
    
    return answer;
}