1095: 最短短路路
内存限制：512 MB
时间限制：1.500 S
评测方式：文本比较
命题人：
提交：53
解决：3
题目描述
「电学学的很好，以后别学了。」
—— 小 R 的物理老师 Lyy
一个 $n$ 点 $m$ 边的 DAG 图。当中，有且仅有点 $1$ 入度为 $0$，为起点；有且仅有点 $n$ 出度为 $0$，为终点。
有若干个点为特殊点。特殊点的出边边权为 $1$，其他边边权均为 $0$。起点和终点绝对不为特殊点。
请求出从起点到终点的最短路中一定不经过的所有特殊点。
输入
第一行 $2$ 个正整数 $n, m$。
接下来一行 $n$ 个正整数 $op_i \in(0, 1)$，表示第 $i$ 个点的特殊性，若 $op_i = 1$，则第 $i$ 个点为特殊点。
接下来 $m$ 行，每行两个正整数 $u, v$，表示存在一条从 $u$ 到 $v$ 的有向边。
输出
一行若干正整数，从小到大输出一定不经过的特殊点的编号，以空格分隔。
样例输入 复制
5 5
0 0 1 0 0
1 2
2 3
3 5
1 4
4 5样例输出 复制
3提示
【数据范围】
对于 $10\%$ 的数据， $n \le 20$。
对于 $60\%$ 的数据， $n \le 10 ^ 5$。
对于 $100\%$ 的数据，$1 \le n, m \le 2 \times 10^6$。
【提示】
- 请注意本题特殊的时限。
- 请注意题面中所有加粗的条件。