Start DFS from each unvisited node. Follow edges until you hit a visited node or close a cycle. Track the path as you go. If you close a cycle, mark all cycle nodes with the cycle length. Then backtrack through the tail, assigning distance as tail length plus cycle length.
Memoization ensures you process each node once. Total time: . This is best since you need to visit every node at least once.