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

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

ru en cn

5945008

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

Росляков Владимир Олегович

Время

14:44<< 31.12.2021 14:48 (27 д. 14:49)

Обработка

14:48 ... 14:48 (3,23 сек.)

Файл

5945008.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 bool first_vertex;
  static Vertex current_vertex;
  static map<Vertex, int> dist;
  static map<Vertex, Vertex> parent;

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

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

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

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

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

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

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

(1 194 b)

0.041s 0.008s 9