[프로그래머스] 합승 택시 요금 (C++)

문제 링크: programmers.co.kr/learn/courses/30/lessons/72413

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

1. 주의할 점

- 모든 정점이 서로 연결되어 있지 않다

- 3번의 다익스트라 알고리즘을 수행해야 한다

 

2. 구현

- Dist[][] 배열을 통해 출발지점, A의 도착지점, B의 도착지점으로부터 각 지점까지의 거리를 저장한다. 초기화는 전부 MAX로 설정한다

- 모든 경로에 대한 정보를 V[] 벡터에 담는다

- 출발지점, A의 도착지점, B의 도착지점에서 시작하는 다익스트라 알고리즘을 수행한다. 이때, 다익스트라 알고리즘은 우선순위큐를 이용한다

- 1~N까지의 지점중에 출발지점+ A의 도착지점+ B의 도착지점까지의 거리가 각각 MAX가 아니면서, 최소거리를 Answer에 저장한다

#define MAX 987654321
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct info{
    int idx,val;
};
struct cmp{
    bool operator()(info &a, info &b){
        return a.val > b.val;
    }
};
info tmp;
vector<info> v[201];
int dist[201][3];

void dijkstra(int start, int flag){
    priority_queue<info,vector<info>,cmp> pq;
    dist[start][flag]=0;
    pq.push({start,0});
    while(!pq.empty()){
        int cidx = pq.top().idx;
        int cv = pq.top().val;
        pq.pop();
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i].idx;
            int nv = v[cidx][i].val;
            if(dist[next][flag] > cv+nv){
                dist[next][flag] = cv+nv;
                pq.push({next,cv+nv});
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = MAX;
    for(int i=1;i<=n;i++)
        for(int j=0;j<3;j++)
            dist[i][j]=MAX;
    for(int i=0;i<fares.size();i++){
        int from = fares[i][0];
        int to = fares[i][1];
        int val = fares[i][2];
        v[from].push_back({to,val});
        v[to].push_back({from,val});
    }
    dijkstra(s,0);
    dijkstra(a,1);
    dijkstra(b,2);
    for(int i=1;i<=n;i++){
        if(dist[i][0]==MAX || dist[i][1]==MAX || dist[i][2]==MAX) continue;
        answer = min(answer,dist[i][0]+dist[i][1]+dist[i][2]);
    }
    return answer;
}