Clash of Kings
A country has V cities. Certain pairs of cities are connected by undirected transport roads between them. There are E such transport roads. There exists a sequence of roads connecting every city in the the country to every other city.
Among the V cities, K of the cities are good cities.
Initially all the cities are free. The country is ruled by two kings. The first king wants no friendship with the second king, while the other king wants friendship with the first king. They now play a game of conquering cities.
The first king selects a good city, then the second king selects a good city and so on; until all the good cities are over.
Suppose at the end some good cities belong to kingdom A and others to B. Distance value between the two kingdoms is defined as the sum of shortest distances between each pair of good cities X and Y such that X belongs to A and Y belongs to B.
The first king wants to maximize the distance value and other king wants to minimize this. Assuming that both play optimally, find out the distance value after the end of the game.
First line contain three space separated integers denoting V, E, and K respectively.
For next E lines, each line contain 3 space separated integers, u v w, denoting that there is an edge from u to v of length w.
The following line contains K space separated integers denoting the indices of the good cities. Indices are given by using 1 based indexation.
A single integer, the maximum possible distance that can be achieved if both kings play optimally.
- 2 ≤ V ≤ 200
- No constraint on E
- 2 ≤ K ≤ 12
- 0 ≤ w ≤ 100
- 1 ≤ u, v ≤ V
- No two u, v pairs repeat in input.
Input: 4 5 3 1 2 5 1 3 2 1 4 3 2 4 2 3 4 2 1 2 4 Output: 7
|Tags||admin2, dynamic-programming, medium, wpc1, wpc1401|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions