[프로그래머스] Level 3. 합승 택시 요금

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

프로그래머스

 

 

처음엔 둘이 같이타거나, 같이안타거나 둘중 하나인줄 알았으나, 예시1을 잘 보면, 합승했다가 중간에 내려서 따로 택시를 타는 경우까지 고려해야한다.

그래서 접근방식은 이렇게된다.

 

K지점까지 함께탑승하는비용 +   K지점에서 A까지 가는 비용 +  K지점에서 B까지 가는 비용 (따로가기때문)

혹은 처음부터 따로가므로 , S에서 A까지 가는  비용 + S에서 B까지가는 비용

 

위의 경우들중 가장 작은 비용을 구하면된다.

이를 위해 A의 다익스트라, B의 다익스트라, S의 다익스트라를 구한다.

S의 다익스트라는 S> K지점까지 함께 가는 경우를 구하기 위함이다.

 

S의 다익스트라를 구한뒤 모든 지점에 대해 S>K , A>K, B>K를 더한 값이 가장 작은 경우를 구한다.

그리고 놓치면 안되는것은 , S>A , S> B로 처음부터  따로 가는경우이다.

 

#include <string>
#include <vector>
#include <climits>

using namespace std;


vector<vector<pair<int,int>>> roots;
vector<int> sdist;
vector<int> adist;
vector<int> bdist;

vector<int> daikstra(int n, int s){
    vector<int> dist (n+1,INT_MAX);
    vector<bool> visited(n+1, false);
    
    dist[s] = 0; 
    int node =s;
    while(node != -1){
        visited[node] = true;
        for(auto item : roots[node]){
            dist[item.first] = min(dist[item.first],dist[node]+item.second);
        }
        
        node= -1;
        for(int i = 1; i<=n; i++){
            if(visited[i] || dist[i] == INT_MAX ) continue;
            if(node == -1 || dist[i]< dist[node]) node = i;
        } 
    }
    
    return dist;
}
int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    
    int answer = INT_MAX;
    roots.resize(n+1, vector<pair<int,int>>());
    for(int i=0; i<fares.size(); i++){
        int s= fares[i][0]; int e= fares[i][1]; int p = fares[i][2];
        roots[s].push_back(make_pair(e,p));
        roots[e].push_back(make_pair(s,p));
    }
    
    sdist = daikstra(n,s);
    adist = daikstra(n,a);
    bdist = daikstra(n,b);
    
    
    answer = adist[s] + bdist[s]; // 한번도 같이타지않는다.
    for(int node = 1; node <=n ; node++){
        answer = min(answer,sdist[node] + adist[node] + bdist[node]); //node번째까지 함께간뒤 
    }
    
    return answer;
}

 

간만에 혼자힘으로 문제를 풀어서 기분이  매우 조크등요