Officials and Roads#11146
In the city of Floville, elections have been held for officials. The city is represented as a connected undirected graph with vertices and edges. Each edge in the graph is described by a triplet of numbers: u_i, v_i, and len_i, indicating an edge between vertices u_i and v_i with a length of len_i.
Each official is provided with housing. Official number resides at vertex h_t on the graph. There are available offices in the city for the officials to work from. If official number is assigned to an office at vertex w_t, they will commute daily from vertex h_t to vertex w_t, always taking the shortest path. Among all possible shortest paths, they choose based on the following rule: reverse the order of the vertices in the path (i.e., from the workplace to home) and select the "lexicographically smallest" path.
For instance, if there are two shortest paths from vertex 0 to vertex 5: 0→1→2→4→5 and 0→3→5, the official will choose the path 0→3→5. This is because, in reverse order (from workplace to home), the paths are 5→4→2→1→0 and 5→3→0. The "lexicographically smallest" is 5→3→0.
All roads (graph edges) along the official's route will be maintained in good condition.
Each official must select one office from the list such that the total length of roads maintained in good condition is maximized.
The first line contains three integers , , and .
— the number of vertices in the graph (N \le 100);
— the number of edges in the graph (M \le 1000);
— the number of officials (T \le 8);
The next lines describe the edges of the graph. Each edge is given in the format: u_i v_i len_i, where len_i is the length of the edge (0 \le u_i, v_i \le n), (len_i \le 100000).
The following line contains integers:
0 \le h_1, h_2, …, h_t, …, h_T \le n — the vertex numbers where the officials' homes are located;
The next line contains integers:
0 \le w_1, w_2, …, w_t, …, w_T \le n — the vertex numbers where the offices for the officials' future work are located.
— the maximum total length of roads that will be guaranteed to be repaired.
0 \le w_{res,1}, w_{res,2}, …, w_{res,t}, …, w_{res,T} \le n — the vertex numbers where the offices for the officials' future work are located, corresponding to the maximum total length of guaranteed repaired roads .
Example 1
Example 10
Example 11
Example 12