分数: 600 点
问题陈述
我们有一个简单的连通无向图 N 顶点和 M 边缘。
顶点编号为 Vertex 1,顶点 2, \dots,顶点 N.
边编号为 Edge 1,边缘 2, \dots,边缘 M。 边缘 i 连接顶点 a_i 和顶点 b_i 双向。 没有直接连接Vertex的边 1 和顶点 N.
每个顶点要么是空的,要么被墙占据。 最初,每个顶点都是空的。
Aoki 将从 Vertex 出发 1 到顶点 N 沿着图表的边缘。 然而,青木不允许移动到被墙占据的顶点。
高桥决定选择一些顶点来建造墙壁,这样青木就无法前往顶点 N 无论他走哪条路。
在 Vertex 上建造一堵墙 i 成本高桥 c_i 日元(日本的货币)。 他无法在 Vertex 上建造一堵墙 1 和顶点 N.
高桥需要多少日元来建造围墙才能满足条件? 另外,打印建造墙壁的方式,以达到最小的成本。
约束
- 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 是高桥将支付的费用
- k 是 Takahashi 建造墙的顶点数
- (p_1,p_2,\dots,p_k) 是高桥将在其上建造墙的一系列顶点
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
如果高桥在 Vertex 上建墙 3 和顶点 4, 支付 3 + 4 = 7 日元,Aoki 无法从 Vertex 出发 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