Тренировки

Тренировка в субботу 23.11

basil-ast
22 ноября 2013, 13:40

Тренировку провожу я, Астахов В. +79263460215. Время начала тренировки 13:30, просьба никому не опаздывать! Позже 14:30 пускать не буду)

Пишем Саратовский ЧФ 2013 

http://acm.math.spbu.ru:8087/~ejudge/team.cgi?contest_id=6635

или на выбор контест с четверга

2 комментария
Подписаться на комментарии к посту

Как решалась М из саратовского контеста?

Решаем для каждой веришины и всех ее искходящих ребер. Делаем обход в ширину по прямым ребрам из этой вершины, для каждой доступной вершины запоминаем через какое ребро мы прошли, разбиваем по такому принципу весь граф на компоненты. Заметим, что кратчайший обходной путь для i-ой вершиныкогда нибудь в последний раз воткнется в i-ую компоненту а потом будет идти внутри этой компоненты. Таким образом для каждой вершины i-ой компоненты найдем длину кратчайшего пути до вершины i (это можно сделать запустив обход в ширину по обратным ребрам для всех вершин до которых идут ребра из первоначальной вершины) и минимальное расстояние до вершины не из i-ой компоненты из которой есть ребро в данную, и найдем минимум по d_1 + d_2 + 1