2 задачки

Решение задачи от Microsoft.
Я так понял условие, что если цикла нет, то getNext(last_element) возвращает что-то уникальное (я обозначил это нулем).

iterator p1 = begin ();
iterator p2 = begin ();
while (p1 != p2)
{
if (getnext (*p2) == 0)
break;
++p2;
if (getnext (*p2) == 0)
break;
++p2;
++p1;
}
if (getnext (*p2) == 0)
цикла нет
else
цикл есть

Оценка очевидна.

2 задачки

Внимательно перечитайте условия:
1) Контрпример: два города, две станции. Оптимальное расположение - в каждый город по станции;
2) N неизвестно.