Jimin's Farm Tour Season II
Time limit2sMemory limit128 MB
Find two edge-disjoint paths from farm 1 to farm N and back that minimize total travel time using no road twice.
- Level
Hard8 of 10
- Topics
- Graph, Shortest path, Greedy
- Solved
- No attempts yet
Problem
Jimin visits the home of Jeongmun, a large landowner. Jeongmun wants to show Jimin the N farms he manages. The farms are numbered from 1 to N, and there are M bidirectional roads between them.
They are currently at farm 1. Jimin wants to visit farm N and then return to farm 1. However, Jimin plans to plant a mine on every road he passes, so he does not want to use any road that has already been used.
Given the time needed to traverse each road, find the minimum total time required to start at farm 1, visit farm N, and return to farm 1. The same road may not be used more than once.
Input
The first line contains two positive integers N and M. N is the number of farms, and M is the number of roads. (3 ≤ N ≤ 1,000, 2 ≤ M ≤ 10,000)
Each of the next M lines contains three positive integers P, Q, and L describing a road. This means there is a road between farm P and farm Q, and traversing it takes L time. (1 ≤ L ≤ 35,000)
The input is guaranteed to contain a valid round trip satisfying the condition.
Output
Output the minimum time needed to start at farm 1, visit farm N, and return to farm 1.