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

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

효율성 생각 안하고 일단 플로이드 와샬을 사용하면 정확성은 맞출 수 있을 것 같아서 시도했는데, 효율성도 바로 통과되었다.

s부터 시작해서 임의의 K노드까지의 최단거리와 K부터 a, b까지의 최단거리를 합한 거리 중 최단거리를 반환해주면 된다.

코드는 아래와 같다.

#include <string>
#include <vector>

using namespace std;

#define pii pair<int, int>
#define INF (1 << 25)

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = INF;
    vector<vector<pii>> graph(n + 1);
    for(auto it : fares) {
        graph[it[0]].push_back( { it[1], it[2]} );
        graph[it[1]].push_back( { it[0], it[2]} );
    }
    vector<vector<int>> cost(n + 1, vector<int>(n + 1, INF));
    for(int i=1;i<=n;i++)
        cost[i][i] = 0;
    
    for(int i=1;i<=n;i++) 
        for(int j=0;j<graph[i].size();j++) 
            cost[i][graph[i][j].first] = graph[i][j].second;
        
    for(int mid=1;mid<=n;mid++) 
        for(int start=1;start<=n;start++) 
            for(int end=1;end<=n;end++) 
                if(cost[start][end] > cost[start][mid] + cost[mid][end])
                    cost[start][end] = cost[start][mid] + cost[mid][end];
    
    for(int mid=1;mid<=n;mid++) {
        int total = cost[s][mid] + cost[mid][a] + cost[mid][b];
        answer = answer > total ? total : answer;
    }
    
    return answer;
}