[伯俊/C+]18352号特定の距離の都市を検索

[伯俊/C+]18352号特定距离的城市检索

1.質問

一部の国では1番からN番までの都市とM本の一方通行道路が存在している.すべての道路の距離は1です.
このとき、ある都市Xから、到達可能なすべての都市において、最短距離Kのすべての都市の番号を出力するプログラムが作成される.また、出発都市Xから出発都市Xまでの最短距離は常に0であると仮定する.
例えば、N=4、K=2、X=1の場合、図形は以下のように組織されていると仮定する.

このとき1番都市から行ける都市のうち、最短距離が2の都市は4番都市しかありません.2番と3番の都市については最短距離が1なので出力しません.

2.入力

1行目は都市の個数N,道路の個数M,距離情報K,出発都市の番号Xを与える.(2≦N≦30000,1≦M≦100000,1≦K≦30000,1≦X≦N)2行目からM行を経て、2つの自然数A,Bをスペース基準で区切る.これは、A番都市からB番都市へ移動する一方通行道路があることを意味する.(1≦A,B≦N)セグメント,AとBは異なる自然数である.

3.出力

Xから到達可能な都市では最短距離Kの全ての都市の番号が1行ずつ昇順に出力される.
このとき到達可能な都市のうち,最短距離Kの都市が1つも存在しなければ−1を出力する.

4.解答

2ダエストラと解釈される.

はすべての幹線の重み付け値が1なので解りやすいです.

は、すべてのパスをINFに初期化し、複数のパスを開始する.

開始ノードのパスを0に変更し、キューを挿入します.

キューから1つずつ取り出し、接続されたノードにアクセスしたことのないノードのパス値を入力し、前のパス値+1を入力します.

のすべての幹線の重みは1であるため、最高値を探したり、優先順位キューを使用したりする必要はありません.

がすべての作業を完了すると、route配列が返され、kと同じ値のインデックスが出力されます.

値出力

が1つもない場合、出力−1.

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

null

6.コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 987654321

using namespace std;

int n, m, k, x;
vector<int> graph[300001];
int route[300001];

void dijkstra() {
  queue<int> q;
  q.push(x);
  route[x] = 0;
  
  while (!q.empty()) {
    int node = q.front();
    q.pop();

    for (int i = 0; i < graph[node].size(); i++) {
      int nextNode = graph[node][i];
      if (route[nextNode] < INF) continue;
      route[nextNode] = route[node] + 1;
      q.push(nextNode);
    }
  }
}

void print() {
  for (int i = 1; i <= n; i++) {
    cout << route[i] << " ";
  }
  cout<<endl;
  
}
int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  cin >> n >> m >> k >> x;
  fill_n(route, n + 1, INF);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    graph[a].push_back(b);
  }
  
  dijkstra();
  
  bool isEmpty = true;
  for (int i = 1; i <= n; i++) {
    if (route[i] == k) {
      cout << i << endl;
      isEmpty = false;
    }
  }

  if (isEmpty) {
    cout << -1;
  }
}