Builder Takahashi

题目描述

我们有一个由 $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 需要多少日元来建造墙以满足该条件？同时，输出一种达到最小花费的建墙方案。

输入格式

输入从标准输入按以下格式给出： $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$

如果存在多种以最小费用满足条件的建墙方式，输出其中任意一种。

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

7
2
3 4

3 2
1 2
2 3
0 1 0

1
1
2

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

3000000000
3
2 3 4

提示

$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$ 输入中的所有数值均为整数。如果 Takahashi 在顶点 $3$ 和顶点 $4$ 上建造墙，支付 $3 + 4 = 7$ 日元，Aoki 将无法从顶点 $1$ 到达顶点 $5$。
不存在花费更少的满足条件的方法，因此答案是 7 日元。

标签: AtCoder|abc239G

来源

AtCoder|abc239G