← 返回题目列表

AtCoder · abc239_g

G. 建造者高桥

中文机器翻译题面 查看原题

分数: 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