[プログラマー]最も遠いノード

14552 ワード
supin2 プログラマ cpp level3 テキストリンク
回答日:2021-08-16

質問する


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

アクセスと解析


1番ノードから最も遠いノードがいくつあるかを知る必要があるのでDijkstraアルゴリズムを考えた.
典型的なDijkstraアルゴリズムを実現し,max element関数とlow boundを用いて最も遠いノードの個数を求めた.

コード#コード#

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

using namespace std;

#define INF 987654321

vector<pair<int, int>> v[20001];

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

int solution(int n, vector<vector<int>> edge) {
    int answer = 0;
    
    for (auto e : edge) {
        v[e[0]].push_back(make_pair(e[1], 1));
        v[e[1]].push_back(make_pair(e[0], 1));
    }
    vector<int> ret = dijkstra(1, n);
    
    for (int i = 0; i <= n; i++) {
        if (ret[i] == INF) {
            ret[i] = -1;
        }
    }
    sort(ret.begin(), ret.end());
    int maxNum = *max_element(ret.begin(), ret.end());
    answer = ret.end() - lower_bound(ret.begin(), ret.end(), maxNum);
    
    return answer;
}

結果



フィードバック


Dijkstraアルゴリズムを知っていれば簡単に解決できる問題です.
Graphiteシリーズ#6:Carbon重合器
Androidカスタムview学習のおすすめ方法を簡単に説明します