2 курс. Программирование на C++. Турнир 3, осень 2021

вход курсы / турниры задачи участники консоль модули компиляторы ключевые слова результаты

ru en cn

5929665

Пользователь

Костюков Максим Сергеевич

Время

00:50<< 24.12.2021 00:50 (20 д. 00:51)

Обработка

00:50 ... 00:51 (3,75 сек.)

Файл

5929665.cpp (CLang++ 5.0.0 + Address Sanitizer)

Турнир

2 курс. Программирование на C++. Турнир 3, осень 2021

Задача

D: Graph visitor

Набор тестов

Ограничения

Время: 1с Память: 4000Мб

Состояние [?]

Принято

код | результаты

[печатать | | ]

≡

#include <map>

using std::map;

template<typename Vertex>
class BfsVisitor {
 private:
  static map<Vertex, int> distances;
  static map<Vertex, Vertex> parents;
  static bool first_vertex;
  static Vertex current_vertex;

public:
  BfsVisitor() {
    distances = map<Vertex, int>();
    parents = map<Vertex, Vertex>();
    first_vertex = true;
  }

void ExamineVertex(const Vertex& vertex) {
    if (first_vertex) {
      first_vertex = false;
      distances[vertex] = 0;
      parents[vertex] = vertex;
      current_vertex = vertex;
      return;
    }
    current_vertex = vertex;
  }

void DiscoverVertex(const Vertex& vertex) {
    distances[vertex] = distances[current_vertex]+1;
    parents[vertex] = current_vertex;
  }

size_t DistanceTo(const Vertex& target) const {
    return distances.at(target);
  }
  Vertex Parent(const Vertex& vertex) const {
    return parents.at(vertex);
  }
};
template <typename T>
map<T, int> BfsVisitor<T>::distances = map<T, int>();

template <typename T>
map<T, T> BfsVisitor<T>::parents = map<T, T>();

template <typename T>
bool BfsVisitor<T>::first_vertex = true;

template <typename T>
T BfsVisitor<T>::current_vertex = T();

(1 235 b)

0.042s 0.008s 9