Computing the Minimum Number of Flight Segments

题目链接：pdf

给一个无向图，一个起点，一个终点，求从起点到终点的路径的边数的最小值。

就是一遍BFS。

// Sun May 14 21:01:40 CST 2017
// Sun May 14 21:20:34 CST 2017

/*
最简单的BFS
 */

#include <iostream>
#include <vector>
#include <queue>

using std::vector;
using std::queue;

int distance(vector<vector<int> > &adj, int s, int t) {
  vector<int> dist(adj.size(), -1);
  queue<int> que;
  dist[s] = 0;
  que.push(s);

  while (!que.empty()) {
    int cur = que.front();
    que.pop();

    for (auto v : adj[cur]) {
      if (-1 == dist[v]) {
	dist[v] = dist[cur] + 1;
	que.push(v);
      }
    }
  }

  return dist[t];
}

int main() {
  int n, m;
  
  while (std::cin >> n >> m) {
    vector<vector<int> > adj(n, vector<int>());
  
    for (int i = 0; i < m; i++) {
      int x, y;
      std::cin >> x >> y;
      adj[x - 1].push_back(y - 1);
      adj[y - 1].push_back(x - 1);
    }
    int s, t;
    std::cin >> s >> t;
    s--, t--;
    std::cout << distance(adj, s, t) << "\n";
  }
}