Graph Theory37 sections · 1633 units
Open in Course

Problem - Longest Flight Route

CSES 1680

You are given a flight network with nn cities and mm flights. Each flight goes from city aa to city bb. You want to find a route from city 11 to city nn that visits the maximum number of cities. If there is no route from 11 to nn, output "IMPOSSIBLE".

Otherwise, output the number of cities in the longest route and the route itself. This is a longest path problem on a DAG, but you are maximizing the number of nodes visited, not edge weights.