Builder Takahashi

Problem Source

AtCoder Beginner Contest 239 G

Problem Description

You are given a connected undirected graph with $n$ vertices and $m$ edges. You may place an obstacle on some vertices (but not on vertex $1$ or vertex $n$). The cost of placing an obstacle on vertex $i$ is $c_i$. You must make vertex $1$ and vertex $n$ disconnected. Find the minimum-cost way to do this.

Input Format

The first line contains two integers $n, m(3\leq n\leq 100, n - 1\leq m \leq \frac{n(n-1)}{2}-1)$.

The following $m$ lines each contain two numbers $a_i, b_i (1\leq a_i < b_i \leq n)$; there are no multiple edges or self-loops, and vertices $1$ and $n$ are not directly connected.

The next line contains $n$ integers $c_1, c_2, \dots, c_n (0 \leq c_i\leq 10^9)$; it is guaranteed that $c_1=c_n=0$.

Output Format

The first line outputs one number: the minimum cost.

The next line outputs a number $k$: the number of vertices where obstacles are placed. The following line contains $k$ numbers: the $k$ vertices where obstacles are placed.

Sample Input

5 5
1 2
2 3
3 5
2 4
4 5
0 8 3 4 0

Sample Output

7
2
3 4

Constraints

$3\leq n\leq 100$; $0\leq c_i\leq 10^9$; $c_1=c_n=0$.

Hint

• Disconnecting vertex 1 from vertex n by removing (obstacle-ing) vertices is exactly a minimum vertex cut (minimum s-t cut on vertices) between 1 and n. Split each vertex into an in- and out-node with capacity $c_i$ (vertices 1 and n have capacity $\infty$), and run max-flow / min-cut.