We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

I do not understand this problem, could someone please help me understand it. First, problem statement indicates that for N cities there are N -1 bidirectional roads. In the explanation of the sample problem there are N cities and 6 possible "routes"(a term which is undefined) using, what to me looks like more than N-1 roads, perhaps some are roads and some are paths or perhaps they are routes... the problem also states that there is guaranteed that there is a path from any city to any other city...and that a path is one or more connected roads...Ok. The given roads, in the sample problem, are [1,2], [2,3], [2,4] which are bidirectional roads. We have a constraint that says a path cannot contain the two same roads(I assume this means [1,2] + [2,1] is invalid) so I assume we have paths: [1,2], [2,1], [2,3], [3,2], [2,4], [4,2], [1,2]+[2,3], [1,2]+[2,4], [3,2]+[2,4], [3,2]+[2,1], [4,2]+[2,1], [4,2]+[2,3] and they satisfy the constraint that there is a path from any city to any other city...so the explanation claims that there is a route [1,2]+[3,4] but it does not appear connected and and to go [1,2]+[2,3]+[3,2]+[2,4] violates the constraint that a path cannot contain the same two roads...perhaps a route is one or more paths and is not subject to the constraint of a path?? is that the case? BUT here is the kicker!!! You need M paths not M routes...so what am I missing? Are the 6 routes discussed [1,2],[1,3],[1,4],[2,3],[2,4],[3,4] or are they roads?? and can they be used as paths to construct other paths?? and why are available to use? confusing. Finally, why not [1,3]+[3,4]??

## Road Maintenance

You are viewing a single comment's thread. Return to all comments →

I do not understand this problem, could someone please help me understand it. First, problem statement indicates that for N cities there are N -1 bidirectional roads. In the explanation of the sample problem there are N cities and 6 possible "routes"(a term which is undefined) using, what to me looks like more than N-1 roads, perhaps some are roads and some are paths or perhaps they are routes... the problem also states that there is guaranteed that there is a path from any city to any other city...and that a path is one or more connected roads...Ok. The given roads, in the sample problem, are [1,2], [2,3], [2,4] which are bidirectional roads. We have a constraint that says a path cannot contain the two same roads(I assume this means [1,2] + [2,1] is invalid) so I assume we have paths: [1,2], [2,1], [2,3], [3,2], [2,4], [4,2], [1,2]+[2,3], [1,2]+[2,4], [3,2]+[2,4], [3,2]+[2,1], [4,2]+[2,1], [4,2]+[2,3] and they satisfy the constraint that there is a path from any city to any other city...so the explanation claims that there is a route [1,2]+[3,4] but it does not appear connected and and to go [1,2]+[2,3]+[3,2]+[2,4] violates the constraint that a path cannot contain the same two roads...perhaps a route is one or more paths and is not subject to the constraint of a path?? is that the case? BUT here is the kicker!!! You need M paths not M routes...so what am I missing? Are the 6 routes discussed [1,2],[1,3],[1,4],[2,3],[2,4],[3,4] or are they roads?? and can they be used as paths to construct other paths?? and why are available to use? confusing. Finally, why not [1,3]+[3,4]??