Вот и наступило лето. Точнее оно наступило 25 дней назад, но ощутил я его только сегодня, потому что я приехал на дачу.
Этот день начинался так, как начинаются все летние деньки, ничем не отличающиеся от остальных дней. Проснулся я, как и полагается, где-то днём, не помню уже точно во сколько. Проснувшись, я решил найти что-нибудь перекусить, но в холодильнике ничего не было. Только висела записка: "Продукты в магазине. Будем поздно. Не скучай".
Понятно, чтобы не умереть с голоду, надо было идти в магазин. Но идти пешком я туда, конечно, не собирался. Велосипед мне на что?) Я быстро нашёл его в гараже и поехал в магазин. Ехал я просто прямо, так как заасфальтированная дорога была только одна, а по песку я как-то не хотел кататься. Я думал, что ничто не сможет испортить мне поездку в магазин. Наивный... На повороте я остановился, точнее меня остановил какой-то дядя, сказав, что придётся объезжать. Разумеется, у меня возник вопрос: "Откуда в деревне нашлись деньги на ремонт дороги, и зачем её вообще было ремонтировать, когда она была в довольно неплохом состоянии?". Лично я знаю места, где дорога выглядит намного хуже. Но ничего не поделаешь, надо было разворачиваться. Теперь, когда ехать пришлось по песку, я включил информатика в своей голове и быстро нашёл кратчайший путь до магазина и обратно.
Приехав домой, я первым делом поел. Кушая, я всё думал об этом ремонте дороги. Грубо говоря, они удалили одно ребро из графа, а я добавил новую вершину в него, когда меня отправили в объезд. И я начал думать над более общей задачей.
Пусть наша программа должна уметь обрабатывать следующие запросы:
Добавить новую вершину в граф.
Удалить вершину из графа.
Добавить новое ребро.
Удалять ребро из графа.
Для пары вершин посчитать кратчайшее расстояние между ними.
Разумеется, что рёбра имеет свой вес. Допускается наличие кратных рёбер, хотя можно и без них. И количество вершин N<=10^5,а рёбер M<=10^5. Все запросы нужно обрабатывать online.
Вот с такой задачей в голове я пошёл загорать на пляж. Вернувшись с речки, я так и не придумал решение данной задачи. Может у кого-нибудь есть идеи, как решать её? Или идеи, как обрабатывать может не все запросы, а только некоторые из них? Пятый запрос нужно обрабатывать всегда.
Comments (0)
