[c++][프로그래머스] 합승 택시 요금

프로그래머스 합승 택시 요금 [2021 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/72413

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

문제 풀이

• 이 문제는 All Pairs Shortest Path를 구하는 알고리즘인 Floyd Warshall 알고리즘을 사용해 해결했습니다. 
• 모든 노드간의 최단 거리(최소 비용)를 구해놓고 [Start -> X(어떤 노드) + X -> A + X -> B] 의 총 합의 최솟값을 리턴합니다.  

코드

#include <vector>

using namespace std;

#define INF 1e7

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    
    vector<vector<int>> dist(n+1, vector<int>(n+1, INF));
    for(int i=1; i<=n; ++i) dist[i][i] = 0;
    
    for(auto fare: fares) {
        dist[fare[0]][fare[1]] = fare[2];
        dist[fare[1]][fare[0]] = fare[2];
    }
    
    // Floyd Warshall Algorithm 
    for(int k=1; k<=n; ++k) {
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
    
    for(int i=1; i<=n; ++i) {
    	// Start -> X + X -> A + X -> B
        int total = dist[s][i] + dist[i][a] + dist[i][b];
        
        answer = min(answer, total);
    }
    
    return answer;
}

실행 결과