Commute Circuit
InterviewTime limit2sMemory limit512 MB
Given a weighted undirected city graph, the office at node 0, and up to 10 employee homes, find the length of the shortest closed route that starts at the office, visits every home, and returns.
- Level
Medium7 of 10
- Topics
- Graph, Shortest path, Dynamic programming, Bit manipulation
- Solved
- No attempts yet
Problem
Wajed works as a driver at a software company. He is responsible for driving employees between their homes and the company's main office. Every day he drives from the main office to the home of every employee to pick them up, then takes them to the office. He should save time and fuel, so he wants to find the best route to do this at the least cost. Your task is to find the shortest route that begins at the company, picks up all the employees, and returns to the company's office.
Input
The first line contains the number of test cases: 0 < T < 100.
Each of the next T test cases begins with a line containing two integers: N, M, the number of intersections N (all numbered from 0 to N-1) and the number of roads M in the city. The company is at the intersection numbered 0. The next M lines each contain three integers X, Y, and D (0 <= X, Y, D <= 1000): intersections X and Y are connected by a bidirectional road of length D. The following line contains a single integer S (1 <= S <= 10), the number of employees that should be gathered. The subsequent S lines each contain one integer indicating the intersection at which each employee's home is located. It is possible to gather all the employees from the company.
Output
For each test case, output a line containing a single integer, the length of the shortest possible trip from the company, gathering all the employees, and returning to the company.