Задача по программированию

[lodin]

Называется "Белорусский вокзал".

Вокзал представляет собой граф, у каждого ребра есть стоимость (= время в пути). У графа две выделенные вершины: город и перрон.

Задача: сделать ориентированными некоторые ребра графа (т.е. расставить полицию с металлоискателями) так, чтобы

1) матожидание затраченного времени при случайном заходе в вокзал и дальнейшем целенаправленном возвращении в город было максимально;

2) существовал неориентированный путь между городом и перроном.

При прочих равных, надо ориентировать минимальное количество ребер.