[プログラマ/C+]配信

[プログラマ/C+]配信

1.質問

Nの村からなる国があります.この国の村ごとに1からNまで番号が付けられています.それぞれの村は双方向に通行する道を結んでおり、異なる村の間を移動するときはこの道を通らなければならない.道路を通るのにかかる時間は道路によって異なります.今の1番村のレストランから食べ物を各村に送りたいです.各村から注文を受けたいのですが、N村の中でK時間以下に配達できる村でしか注文を受けられないと思います.次に、N=5、K=3の例を示します.

上図1番村のレストランは[1,2,4,5]番村まで3時間以下で配達できます.しかし、3番村までは3時間以内に配送できるルートがないので、3番村は注文を受け付けません.このため、1番村のレストランで出前の注文を受けられる村は4つある.
村落個数N、各村落を結ぶ道路の情報路、配達可能な食べ物の時間Kをパラメータとした場合は、解関数を完了し、食べ物の注文を受けられる村落個数を返してください.

2.制限

村の個数Nは1以上50以下の自然数である.

道路の長さ(道路情報の個数)は1または2000以下である.

道路の各要素は、村を結ぶ各道路の情報を表す.

道路は、3つの長さの配列であり、順序(a、b、c)である.
-a,b(1≦a,b≦N,a!=b)は道路が接続された2つの村の番号であり、c(1≦c≦10000,cは自然数)は道路を通過するのに要する時間である.
-2つの村a,bを結ぶ道は複数ある.
-1つの道路の情報は何度も繰り返され、提供できません.

Kは配送可能な時間を示し、500000を超えない.

任意の2つの村の間には常に移動可能な経路が存在する.

1番村のレストランはK以下の時間内に食事を送ることができる村の数を返してください.

3.解答

다익스트라

ドエストラアルゴリズムを用いて各村の最短距離を求めた.

4.最初のコードと異なる点

双方向とは考えられなかった.

5.コード

#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9

using namespace std;

int solution(int N, vector<vector<int> > road, int K) {
    int answer=0;
    
    vector<pair<int, int> > graph[51];
    int d[51];
    fill(d, d + 51, INF);
    
    for(int i=0; i<road.size(); ++i) {
        graph[road[i][0]].push_back({road[i][1], road[i][2]});
        graph[road[i][1]].push_back({road[i][0], road[i][2]});
    }
    
    priority_queue<pair<int, int> > pq;
    pq.push({ 0, 1 });
    d[1] = 0;
    
    while (!pq.empty()) { 
        int dist = -pq.top().first;
        int now = pq.top().second;
        pq.pop();
        
        if (d[now] < dist) continue;
        for (int i = 0; i < graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            if (cost < d[graph[now][i].first]) {
                d[graph[now][i].first] = cost;
                pq.push(make_pair(-cost, graph[now][i].first));
            }
        }
    }
    for(int i=1; i<=N; ++i) {
        if(d[i] <= K) answer++;
    }
    
    return answer;
}