设置地图 - Problem

我打算在路径上安装地图。该路径可以看作是一个由 $N$ 个顶点（编号从 $1$ 到 $N$）和 $M$ 条有向边组成的图。图中不存在自环，也不存在重边。

该路径有一个起点 $S$ 和一个终点 $E$。为了方便起见，我希望安装地图，使得从 $S$ 到 $E$ 的所有路径都至少经过 $K$ 个安装了地图的顶点。

每个顶点（包括起点和终点）最多只能安装一个地图，在顶点 $v$ 安装地图的费用为 $C_v$。

我希望以最低的成本完成地图安装。请确定是否可以满足上述条件，如果可以，请输出应该在哪些顶点安装地图，使得总成本最小。

第一行包含三个整数 $N$、$M$ 和 $K$，分别表示顶点数、$M$ 条边以及最少需要经过的地图数量 ($2 \le N \le 200, 1 \le M \le 500, 1 \le K \le 5$)。

第二行包含两个整数 $S$ 和 $E$，分别表示起点和终点 ($1 \le S, E \le N, S \neq E$)。

第三行包含 $N$ 个整数 $C_1, C_2, \dots, C_N$，表示在顶点 $1, 2, \dots, N$ 安装地图的费用 ($1 \le C_i \le 10^7$)。

接下来的 $M$ 行描述边。第 $j$ 行包含两个整数 $u_j$ 和 $v_j$，表示第 $j$ 条边的起点和终点 ($1 \le u_j, v_j \le N, u_j \neq v_j$)。

保证路径图中不包含自环和重边。

如果无法满足条件，第一行输出 $-1$。

如果可以安装地图，第一行输出需要安装地图的顶点数量 $P$，使得总成本最小。第二行输出这 $P$ 个顶点的编号，用空格分隔，顺序不限。如果存在多种可能的答案，输出其中任意一种即可。

-1

7 11 1
1 7
100 5 7 16 11 12 100
1 2
1 3
1 4
1 5
2 3
2 6
3 6
4 3
4 7
5 7
6 7

3
5 6 4

QOJ.ac