FunctionRacerProblemsRace

Second Best Trip

HardGraphsPython, JavaScript, TypeScript, Java, C++

There are n towns numbered 0 to n - 1. Each entry of roads is [a, b, length]: a road between towns a and b that can be driven in both directions. Several roads may join the same two towns.

A trip from start to goal may use roads and pass towns as often as it likes, also start and goal themselves. Its length is the sum of the roads driven.

Return the length of the shortest trip that is strictly longer than the shortest trip of all. Return -1 if there is no such trip.

Example 1

n 3
roads [[0,1,2],[1,2,3],[0,2,6]]
start 0
goal 2
returns 6

The shortest trip goes over town 1 and is 2 + 3 = 5 long. The direct road, 6 long, is the next best.

Example 2

n 2
roads [[0,1,4]]
start 0
goal 1
returns 12

The only way to make the trip longer is to drive the road three times: 4 + 4 + 4.

Example 3

n 3
roads [[0,1,5]]
start 0
goal 2
returns -1

No road leads to town 2, so there is no trip at all.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems