Three Robots
Time limit2sMemory limit512 MB
Given a connected weighted graph and three robot start vertices, find the earliest time all three can meet at one vertex, where each robot may wait or move along edges.
- Level
Medium7 of 10
- Topics
- Graph, Shortest path, Heap, Simulation
- Solved
- No attempts yet
Problem
An undirected weighted graph G is given, and G is connected, that is, any two vertices in G are connected by a path. Three robots are exploring G along edges. The weight of each edge is the time a robot spends passing through it. All robots have the same speed, and two or more robots may pass through the same edge at the same time. At some instant during the explorations, all three robots must meet at a vertex to share their information. This is called a rendezvous.
Initially, the three robots are on specified vertices. Of course, two or more robots may be located on the same vertex. Also, all three robots start moving simultaneously. We want to find the minimum time needed to achieve the first rendezvous.
Figure L.1
For example, suppose the three robots are initially located on vertices 1, 5, and 7 in Figure L.1. A robot on vertex 1 moving to vertex 9 requires at least 9 time units. Also, the robots on vertices 5 and 7 require at least 8 and 3 time units, respectively, to travel to vertex 9. So a rendezvous at vertex 9 requires at least 9 time units, and this is the minimum time needed for the first rendezvous. Of course, the first rendezvous can also happen at vertex 1 or 4, and it also requires the minimum time of 9.
Given a weighted and connected graph G and the initial locations of three robots, write a program to find the minimum time needed to achieve the first rendezvous.
Input
Your program reads from standard input. The input starts with a line containing two integers, N and M (1 ≤ N ≤ 20,000, N − 1 ≤ M ≤ 100,000), where N and M are the numbers of vertices and edges of G, respectively. The vertices of G are represented by 1, 2, … , N. In each of the following M lines, three integers a, b, and t (1 ≤ a ≠ b ≤ N, 1 ≤ t ≤ 10,000) are given, where an edge connects the two vertices a and b, and its weight is t. The last (M + 2)-th line contains three integers u, v, and w, which are the initial locations of the three robots (1 ≤ u, v, w ≤ N). Of course, at least two of the three robots may be initially located on the same vertex.
Output
Your program writes to standard output. Print exactly one line containing the minimum time needed to achieve the first rendezvous.