프로그래머스 - 합승 택시 요금 (Cpp)

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

문제 풀이

모든 간선의 weight가 음수가 아닌 값, 시작점 s에서 도착할 수 있는 거리의 최소 비용을 구하는 문제라 다익스트라를 이용해 문제를 해결할 수 있다.

시작점 s에서 시작해 x점까지 같이 이동하는 최소 비용 + x점에서 시작해 a점까지 이동하는 최소 비용 + x점에서 시작해 b점까지 이동하는 최소 비용 중에서 가장 값이 작은 값을 찾는 문제다.
원리는 간단하지만 다익스트라에 대해 잘 알고 있어야 풀 수 있는 문제다.

void dijkstra(int node) {
    for (int i = 1; i < 220; i++) {
        dist[node][i] = INF;
    }

    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, node));
    dist[node][node] = 0;

    while (!pq.empty()) {
        int nodeDist = -pq.top().first;
        int cntNode = pq.top().second;
        pq.pop();

        if (dist[node][cntNode] != nodeDist) {
            continue;
        }

        for (pair<int, int> vertex : graph[cntNode]) {
            int nextWeight = nodeDist + vertex.second;
            int nextNode = vertex.first;

            if (nextWeight < dist[node][nextNode]) {
                dist[node][nextNode] = nextWeight;
                pq.push(make_pair(-nextWeight, nextNode));
            }
        }
    }
}

전체 소스 코드

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

const int INF = 987654321;
long long dist[220][220];
vector<vector<pair<int, int>>> graph;

void dijkstra(int node) {
    for (int i = 1; i < 220; i++) {
        dist[node][i] = INF;
    }

    priority_queue<pair<int, int>> pq;
    pq.push(make_pair(0, node));
    dist[node][node] = 0;

    while (!pq.empty()) {
        int nodeDist = -pq.top().first;
        int cntNode = pq.top().second;
        pq.pop();

        if (dist[node][cntNode] != nodeDist) {
            continue;
        }

        for (pair<int, int> vertex : graph[cntNode]) {
            int nextWeight = nodeDist + vertex.second;
            int nextNode = vertex.first;

            if (nextWeight < dist[node][nextNode]) {
                dist[node][nextNode] = nextWeight;
                pq.push(make_pair(-nextWeight, nextNode));
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    graph = vector<vector<pair<int, int>>>(n + 1);

    for (vector<int> fare : fares) {
        int start = fare[0];
        int end = fare[1];
        int weight = fare[2];

        graph[start].push_back(make_pair(end, weight));
        graph[end].push_back(make_pair(start, weight));
    }
    // dijkstra_start(s);

    for (int i = 1; i <= n; i++) {
        dijkstra(i);
    }

    long long minValue = INF;
    for (int i = 1; i <= n; i++) {
        if (minValue > dist[s][i] + dist[i][a] + dist[i][b]) {
            minValue = dist[s][i] + dist[i][a] + dist[i][b];
        }
    }
    answer = minValue;

    return answer;
}