Avionska presedanja - Rešenje

Postavka

Aerodromi i letovi između njih se mogu predstaviti usmerenim grafom. Najkraće puteve u tom grafu možemo najjednostavnije pronaći pretragom u širinu. Nju implementiramo tako što u red stavljamo čvorove u redosledu njihovog rastojanja od polaznog čvora. Na početku stavljamo polazni čvor, a zatim u svakom koraku skidamo čvor sa početka reda i u red dodajemo njegove susede koji ranije nisu posećeni. Uz svaki čvor u red postavljamo i njegovo rastojanje od polaznog čvora. U trenutku kada u red treba staviti dolazni čvor, znamo njegovo najkraće rastojanje. Ako se red isprazni pre nego što se dolazni čvor postavi u njega, onda polazni i dolazni čvor nisu povezani.

// pretragom u sirinu odredjujemo najkrace rastojanje izmedju dva aerodro
// graf je predstavljen listama povezanosti, pri čemu su oznake
// cvorova niske, a ne redni brojevi
int brojPresedanjaBFS(const string& aerodromOd, const string& aerodromDo,
                      const map<string, vector<string>>& letovi) {
  // skup posecenih aerodroma
  set<string> posecen;
  // red potreban za implementaciju obilaska u sirinu
  queue<pair<string, int>> red;
  // krecemo od polaznog aerodroma
  red.emplace(aerodromOd, 0);
  while (!red.empty()) {
    // uzimamo tekuci aerodrom iz reda i njegovo rastojanje od polaznog
    string aerodrom;
    int rastojanje;
    tie(aerodrom, rastojanje) = red.front();
    red.pop();
    posecen.insert(aerodrom);

    // lista suseda tekuceg aerdroma
    auto it = letovi.find(aerodrom);
    if (it != letovi.end()) {
      // prolazimo kroz sve letove sa tekuceg aerodroma
      for (const string& sused : it->second) {
        // ako su poseceni, preskacemo ih
        if (posecen.find(sused) != posecen.end())
          continue;
        // ako smo dostigli dolanzi aerodrom, znamo najkrace
        // rastojanje do njega
        if (sused == aerodromDo)
          return rastojanje+1;
        // dodajemo susedni aerodrom u red
        red.emplace(susedni, rastojanje+1);
      }
    }
  }
  // dolazni aerodrom nije dostizan
  return -1;
}

int main() {
  // graf je predstavljen listama povezanosti, pri čemu su oznake
  // cvorova niske, a ne redni brojevi
  int m;
  cin >> m;
  map<string, vector<string>> letovi;
  for (int i = 0; i < m; i++) {
    string aerodromOd, aerodromDo;
    cin >> aerodromOd >> aerodromDo;
    letovi[aerodromOd].push_back(aerodromDo);
  }

  // odgovaramo na k upita
  int k;
  cin >> k;
  for (int i = 0; i < k; i++) {
    string aerodromOd, aerodromDo;
    cin >> aerodromOd >> aerodromDo;
    int broj = brojPresedanjaBFS(aerodromOd, aerodromDo, letovi);
    if (broj == -1)
      cout << "ne" << endl;
    else
      cout << broj << endl;
  }
  return 0;
}
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <queue>
#include <set>

using namespace std;

// pretragom u sirinu odredjujemo najkrace rastojanje izmedju dva aerodro
// graf je predstavljen listama povezanosti, pri čemu su oznake
// cvorova niske, a ne redni brojevi
int brojPresedanjaBFS(const string& aerodromOd, const string& aerodromDo,
                      const map<string, vector<string>>& letovi) {
  // skup posecenih aerodroma
  set<string> posecen;
  // red potreban za implementaciju obilaska u sirinu
  queue<pair<string, int>> red;
  // krecemo od polaznog aerodroma
  red.emplace(aerodromOd, 0);
  while (!red.empty()) {
    // uzimamo tekuci aerodrom iz reda i njegovo rastojanje od polaznog
    string aerodrom;
    int rastojanje;
    tie(aerodrom, rastojanje) = red.front();
    red.pop();
    posecen.insert(aerodrom);

    // lista suseda tekuceg aerdroma
    auto it = letovi.find(aerodrom);
    if (it != letovi.end()) {
      // prolazimo kroz sve letove sa tekuceg aerodroma
      for (const string& sused : it->second) {
        // ako su poseceni, preskacemo ih
        if (posecen.find(sused) != posecen.end())
          continue;
        // ako smo dostigli dolanzi aerodrom, znamo najkrace
        // rastojanje do njega
        if (sused == aerodromDo)
          return rastojanje+1;
        // dodajemo susedni aerodrom u red
        red.emplace(susedni, rastojanje+1);
      }
    }
  }
  // dolazni aerodrom nije dostizan
  return -1;
}

int main() {
  // graf je predstavljen listama povezanosti, pri čemu su oznake
  // cvorova niske, a ne redni brojevi
  int m;
  cin >> m;
  map<string, vector<string>> letovi;
  for (int i = 0; i < m; i++) {
    string aerodromOd, aerodromDo;
    cin >> aerodromOd >> aerodromDo;
    letovi[aerodromOd].push_back(aerodromDo);
  }

  // odgovaramo na k upita
  int k;
  cin >> k;
  for (int i = 0; i < k; i++) {
    string aerodromOd, aerodromDo;
    cin >> aerodromOd >> aerodromDo;
    int broj = brojPresedanjaBFS(aerodromOd, aerodromDo, letovi);
    if (broj == -1)
      cout << "ne" << endl;
    else
      cout << broj << endl;
  }
  return 0;
}