[プログラマー]タクシー料金の併用

14970 ワード
level3 2021 KAKAO BLIND RECRUITMENT プログラマ supin2 cpp テキストリンク
回答日:2021年-08-05

質問する


質問リンク:https://programmers.co.kr/learn/courses/30/lessons/72413

アクセスと解析


以前はFloyd-Warshallアルゴリズムで解きましたが、今回はDijkstraアルゴリズムで解きます.
一般的なDijkstraアルゴリズムにより,与えられたs,a,bからすべてのノードに到達する最短経路を求めた.
そして、始点(s)から移動タクシーに乗り合わせる任意のノード(x)までの距離と、到着地(a,b)からノード(x)までのそれぞれの乗り換える距離の和の最短距離を求めた.

コード#コード#

#include <string>
#include <vector>
#include <queue>

using namespace std;

#define INF 987654321

vector<pair<int, int>> map[201];

vector<int> dijkstra(int start) {
    vector<int> distance(201, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    distance[start] = 0;
    pq.push(make_pair(0, start));
    
    while (!pq.empty()) {
        int cost = pq.top().first;
        int now = pq.top().second;
        pq.pop();
        
        if (distance[now] < cost) {
            continue;
        }
        for (int i = 0; i < map[now].size(); i++) {
            int next = map[now][i].first;
            int nCost = cost + map[now][i].second;
            
            if (distance[next] > nCost) {
                distance[next] = nCost;
                pq.push(make_pair(nCost, next));
            }
        }
    }
    return distance;
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 0;
    
    for (auto f : fares) {
        map[f[0]].push_back(make_pair(f[1], f[2]));
        map[f[1]].push_back(make_pair(f[0], f[2]));
    }
    vector<int> from_s = dijkstra(s); // s에서 출발한 최단거리
    vector<int> from_a = dijkstra(a); // a에서 출발한 최단거리
    vector<int> from_b = dijkstra(b); // b에서 출발한 최단거리
    
    answer = from_s[a] + from_s[b];
    for (int i = 1; i <= n; i++) {
        if (i == s) {
            continue;
        }
        if (from_s[i] == INF || from_a[i] == INF || from_b[i] == INF) {
            continue;
        }
        answer = min(answer, from_s[i] + from_a[i] + from_b[i]);
    }
    return answer;
}

結果



フィードバック


同じ問題を違うものにしようとする
08 Html Helper
カウントダウンコードは秒まで正確です