Расстояние в графах (12 ноября 2015, Глеб)

Если в каких-то задачах граф взвешенный, то вес неотрицательные.
1. За O(n + m) найти в незвешенном неорграфе цикл нечетной длины.
2. bfs на графе с весами из {0, 1} (вместо очереди дек)
3. bfs на графе с весами из {1, 2} (три очереди)
4. Кратчайший цикл в графе, проходящий через данное ребро за O(E)
5. Кратчайший цикл в графе за O(E²), за O(VE)
6. В неориентированном графе за O(VE) найти две вершины на максимальном расстоянии друг от друга.
7. Дан взвешенный неограф. Найти путь из s в t такой, что максимальное ребро минимально.
8. Дан взвешенный неограф. Найти путь из s в t такой, что сумма двух максимальных ребер на пути минимальна. А если орграф?
9. Дан взвешенный неограф. Найти все рёбра, лежащие на кратчайших путях из s в t.
10. Дан взвешенный орграф. Найти кратчайший путь, проходящий по всем k ≤ 10 выделенным вершинам.
11. Ацикличный граф: матрица достижимости за O(VE/w) (w − размер машинного слова)
12. Произвольный граф: матрица достижимости за O(V³/w) (оптимизируем Флойда)
13. [не успеем] Задача: дана бесконечная прямая дорога ширины W. На дороге есть точечные препятствия в точках x_i, y_i.
    Круглую машину какого максимального радиуса мы сможем провести с -∞ до +∞?
14. [не успеем] Дан взвешенный неограф. Найти длину кратчайшего среди путей из s в t, проходящих хотя бы по одной вершине не из множества A.