Programmers : 합승 택시 요금

문제링크

풀이상세

다익스트라 / 플로이드

풀이요약

1. 프로도와 무지가 $S$ 를 기점으로 각자의 도착지점까지 간다는 것은, 어떤 경우든 $S$ 와 도착지점은 이어질 수 밖에 없다.
2. 그렇다면 배열 3개를 만들어서, $S$ 에서 각 지점까지의 최단 거리와, $A$ 에서 각 지점까지의 최단 거리, $B$ 에서 각 지점까지의 최단 거리를 구한후, 임의의 $N$ 노드를 거쳤을 때의 최단 값을 구하면 된다.
3. 즉, $S→N$ 까지가 함께 가는 거리이고, 나머지가 $N→A$ , $N→B$ 까지 가는 거리 비용이다. $S==N$ 동일한 경우가 서로 동행하지 않고 간 거리 비용이다.

배운점

• 플로이드 보다 다익스트라가 빠를 수 있다는 걸 안 문제, 플로이드는 전체적 범위를 찾는 것에 있어서 다익스트라보다 빠르지만, 최적해를 찾아 일부 노드만 탐색해서 답이 나온다면 일반적으로 다익스트라가 압도적으로 빠르다. $O(N^3) > O(KN)$

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int ans, dp1[201],dp2[201],dp3[201];
const int INF = 2e8+4;
vector<pair<int,int>> list[201];

void dijstra(int st, int n, int s[]) {
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    fill(s+1, s+n+1, INF);
    pq.push({0, st});
    s[st]=0;
    while(!pq.empty()) {
        pair<int,int> curr = pq.top();
        pq.pop();
        for(pair<int,int> next : list[curr.second]) {
            if(s[next.second] > curr.first+next.first) {
                s[next.second] = curr.first+next.first;
                pq.push({s[next.second], next.second});
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    for(int i=0; i<fares.size(); i++) {
        list[fares[i][0]].push_back({fares[i][2],fares[i][1]});
        list[fares[i][1]].push_back({fares[i][2],fares[i][0]});
    }
    
    dijstra(s,n,dp1);
    dijstra(a,n,dp2);
    dijstra(b,n,dp3);

    for(int d=1; d<=n; d++) {
        int sum = dp1[d] + dp2[d] + dp3[d];    
        if(sum < answer) answer = sum;
    }
    return answer;
}