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

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

ru en cn

5940655

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

Долматов Кирилл Дмитриевич

Время

01:45<< 28.12.2021 01:45 (24 д. 01:46)

Обработка

01:45 ... 01:45 (4,13 сек.)

Файл

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

Турнир

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

Задача

D: Graph visitor

Набор тестов

Ограничения

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

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

Принято

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

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

≡

#include <map>

template<typename Vertex>
class BfsVisitor {
 public:
    BfsVisitor() {
        dist = std::map<Vertex, int>();
        parent = std::map<Vertex, Vertex>();
        current_vert = (Vertex)(-1);
    }

void ExamineVertex(const Vertex &vertex) {
        current_vert = vertex;
    }

void DiscoverVertex(const Vertex &vertex) {
        if (current_vert == (Vertex)(-1)) {
            dist[vertex] = 0;
            parent[vertex] = vertex;
        } else {
            dist[vertex] = dist[current_vert] + 1;
            parent[vertex] = current_vert;
        }
    }

size_t DistanceTo(const Vertex &target) const {
        return dist.at(target);
    }

Vertex Parent(const Vertex &vertex) const {
        return parent.at(vertex);
    }

private:
    static std::map<Vertex, int> dist;
    static std::map<Vertex, Vertex> parent;
    static Vertex current_vert;
};

template <typename T>
std::map<T, int> BfsVisitor<T>::dist = std::map<T, int>();

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

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

(1 167 b)

0.048s 0.008s 9