합승 택시 요금

예전에 풀어본 문제를 다시 푸는것도 있지만 너무 오래 전에 풀었던 문제라 사실상 아예 새롭게 풀어본 느낌이다.

바로 전 문제에서 다익스트라에 자신감? 이 조금 생겼어서 바로 도전했는데 확실히 다른 점을 이번에 느꼈다.

먼저, 앞서 내가 다익스트라를 BFS로 구현할때 탐색 과정에서 아무러 조건문을 안넣었는데 여기서는 넣어줘야 했다. 왜냐? 바로 Undirected Graph 형식이기 때문에 중복으로 확인하는 과정에서 조건문이 없으면 TLE 가 걸리기 때문이다.

다익스트라에서 조건문을 안넣는게 국룰로 생각했는데 이렇게 Undirected 면 꼭 넣어줘야겠다.

그리고 문제를 풀다가 느낀건데 이 문제는 확실히 정점 하나에서 각자 최소 값으로 갈 수 있는 거리를 구해야 한다고 느꼈다. 그렇기 때문에 s, a, b 정점을 시작으로 최소 값을 구했다.

일반적으로 다익스트라는 한 정점에서 다른 모든 정점을 갈 수 있다는 가정하에 그 정점을 중심으로 가장 최단 거리를 탐색하게 된다.

그렇기 떄문에 각자 지점에서 최단 거리를 찾았으면 3이 겹쳐도 가장 짧은 구간을 구하면 됐다.

또 한번 성장한 느낌!

#include <string>
#include <vector>
#include <bits/stdc++.h> 
using namespace std;


void bfs(vector<vector<pair<int,int>>>& adj, vector<int>& dist, int node){
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq; 
    pq.push({0,node}); 
    dist[node] = 0; 
    
    while(!pq.empty()){
        int size = pq.size();
        for(int i = 0; i < size; i++){
            vector<int> v = pq.top();
            pq.pop(); 
            
            int distance = v[0], currNode = v[1]; 
            
            for(pair<int,int>& p : adj[currNode]){
                int nextNode = p.first, addDist = p.second; 
                //cout << nextNode << endl; 
                //pq.push({distance + addDist, nextNode}); 
                //dist[currNode] = distance; 
                if(distance + addDist < dist[nextNode]){
                    dist[nextNode] = distance + addDist; 
                    pq.push({distance + addDist, nextNode}); 
                }
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INT_MAX;
    vector<vector<pair<int,int>>> adj(n+1); 
    vector<int> distStart(n+1,INT_MAX); 
    vector<int> distA(n+1,INT_MAX); 
    vector<int> distB(n+1,INT_MAX); 
    for(vector<int>& v : fares){
        int from = v[0], to = v[1], weight = v[2]; 
        adj[from].push_back({to,weight}); 
        adj[to].push_back({from,weight}); 
    }
    
    bfs(adj,distStart,s); 
    bfs(adj,distA,a);
    bfs(adj,distB,b); 
    
    for(int i = 1; i <= n; i++){
        answer = min(answer,distStart[i] + distA[i] + distB[i]); 
    }
    
    
    return answer;
}