102396: [AtCoder]ABC239 G - Builder Takahashi
Description
Score : $600$ points
Problem Statement
We have a simple connected undirected graph with $N$ vertices and $M$ edges.
The vertices are numbered as Vertex $1$, Vertex $2$, $\dots$, Vertex $N$.
The edges are numbered as Edge $1$, Edge $2$, $\dots$, Edge $M$. Edge $i$ connects Vertex $a_i$ and Vertex $b_i$ bidirectionally. There is no edge that directly connects Vertex $1$ and Vertex $N$.
Each vertex is either empty or occupied by a wall. Initially, every vertex is empty.
Aoki is going to travel from Vertex $1$ to Vertex $N$ along the edges on the graph. However, Aoki is not allowed to move to a vertex occupied by a wall.
Takahashi has decided to choose some of the vertices to build walls on, so that Aoki cannot travel to Vertex $N$ no matter which route he takes.
Building a wall on Vertex $i$ costs Takahashi $c_i$ yen (the currency of Japan). He cannot build a wall on Vertex $1$ and Vertex $N$.
How many yens is required for Takahashi to build walls so that the conditions is satisfied? Also, print the way of building walls to achieve the minimum cost.
Constraints
- $3 \leq N \leq 100$
- $N - 1 \leq M \leq \frac{N(N-1)}{2} - 1$
- $1 \leq a_i \lt b_i \leq N$ $(1 \leq i \leq M)$
- $(a_i, b_i) \neq (1, N)$
- The given graph is simple and connected.
- $1 \leq c_{i} \leq 10^9$ $(2 \leq i \leq N-1)$
- $c_1 = c_N = 0$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$ $c_1$ $c_2$ $\dots$ $c_N$
Output
Print in the following format. Here, $C,k$, and $p_i$ are defined as follows.
- $C$ is the cost that Takahashi will pay
- $k$ is the number of vertices for Takahashi to build walls on
- $(p_1,p_2,\dots,p_k)$ is a sequence of vertices on which Takahashi will build walls
$C$ $k$ $p_1$ $p_2$ $\dots$ $p_k$
If there are multiple ways to build walls to satisfy the conditions with the minimum cost, print any of them.
Sample Input 1
5 5 1 2 2 3 3 5 2 4 4 5 0 8 3 4 0
Sample Output 1
7 2 3 4
If Takahashi builds walls on Vertex $3$ and Vertex $4$, paying $3 + 4 = 7$ yen, Aoki is unable to travel from Vertex $1$ to Vertex $5$.
There is no way to satisfy the condition with less cost, so $7$ yen is the answer.
Sample Input 2
3 2 1 2 2 3 0 1 0
Sample Output 2
1 1 2
Sample Input 3
5 9 1 2 1 3 1 4 2 3 2 4 2 5 3 4 3 5 4 5 0 1000000000 1000000000 1000000000 0
Sample Output 3
3000000000 3 2 3 4
Input
题意翻译
### 题目描述 给定一张 $n$ 个点 $m$ 条边的连通无向图,要求在某些点(不能为 $1$ 号点或者 $n$ 号点)设立障碍,在 $i$ 号点建立障碍的费用为 $c_i$,要使得 $1$ 号点和 $n$ 号点不连通,求最小花费的方案。 ### 输入格式 第一行两个整数 $n,m(3\leq n\leq 100,n−1\leq m\leq \frac{n(n−1)}{2}−1)$。 接下来 $m$ 行,每行两个数 $a_i,b_i(1\leq ai < bi\leq n)$,保证没有重边自环,并且 $1$ 与 $n$ 不直接相连。 接下来一行 $n$ 个整数 $c_1,c_2,…,c_n(0\le ci\le 10^9)$,保证 $c_1=c_n=0$。 ### 输出格式 第一行输出一个数,表示最小的花费。 接下来输出一个数 $k$,表示建立障碍的个数。接下来一行 $k$ 个数,表示建立障碍的 $k$ 个点。Output
问题描述
我们有一个简单的连通无向图,有$N$个顶点和$M$条边。
顶点编号为顶点$1$、顶点$2$、$\dots$、顶点$N$。
边编号为边$1$、边$2$、$\dots$、边$M$。边$i$双向连接顶点$a_i$和顶点$b_i$。不存在直接连接顶点$1$和顶点$N$的边。
每个顶点要么为空,要么被墙占据。最初,每个顶点都是空的。
Aoki打算沿着图中的边从顶点$1$前往顶点$N$。然而,Aoki不允许移动到被墙占据的顶点。
Takahashi决定选择一些顶点来建造墙,以便无论Aoki选择哪条路线,都无法到达顶点$N$。
在顶点$i$建造墙需要花费Takahashi$c_i$日元(日本的货币)。**他不能在顶点$1$和顶点$N$建造墙。**
Takahashi需要多少钱来建造墙,以满足条件?同时,打印出实现最低成本的建造墙的方式。
约束
- $3 \leq N \leq 100$
- $N - 1 \leq M \leq \frac{N(N-1)}{2} - 1$
- $1 \leq a_i \lt b_i \leq N$ $(1 \leq i \leq M)$
- $(a_i, b_i) \neq (1, N)$
- 给定的图是简单且连通的。
- $1 \leq c_{i} \leq 10^9$ $(2 \leq i \leq N-1)$
- $c_1 = c_N = 0$
- 输入中的所有值都是整数。
输入
输入以标准输入的以下格式给出:
$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_M$ $b_M$ $c_1$ $c_2$ $\dots$ $c_N$
输出
以以下格式打印。在这里,$C,k$和$p_i$定义如下。
- $C$是Takahashi将支付的费用
- $k$是Takahashi需要在上面建造墙的顶点数
- $(p_1,p_2,\dots,p_k)$是Takahashi将在上面建造墙的顶点序列
$C$ $k$ $p_1$ $p_2$ $\dots$ $p_k$
如果有多种满足条件的方法来建造墙,以最低成本打印其中的任何一种。
样例输入1
5 5 1 2 2 3 3 5 2 4 4 5 0 8 3 4 0
样例输出1
7 2 3 4
如果Takahashi在顶点$3$和顶点$4$上建造墙,支付$3 + 4 = 7$日元,Aoki将无法从顶点$1$前往顶点$5$。
没有以更低成本满足条件的方法,因此$7$日元是答案。
样例输入2
3 2 1 2 2 3 0 1 0
样例输出2
1 1 2
样例输入3
5 9 1 2 1 3 1 4 2 3 2 4 2 5 3 4 3 5 4 5 0 1000000000 1000000000 1000000000 0
样例输出3
3000000000 3 2 3 4