不在场的证明(Checking an Alibi)

题目描述

谷仓里发现谷物被盗！FJ 正试图从 $C$ 只奶牛里找出那个偷谷物的罪犯。幸运的是，一个恰好路过的卫星拍下谷物被盗前 $M$ 秒的农场的图片。这样约翰就能通过牛们的位置来判断谁有足够的时间来盗窃谷物。

约翰农场有 $F$ 片草地，标号 $1$ 到 $F$，还有 $P$ 条双向路连接着它们。通过这些路需要的时间在 $1$ 到 $7\times 10^4$ 秒的范围内。草地 $1$ 上建有那个被盗的谷仓。给出农场地图，以及卫星照片里每只牛所在的位置，请判断哪些牛有可能犯罪。

请注意：数据里可能存在重边（起点和终点相同的边）。

题目中所说的“可能犯罪的牛”指的是在 $M$ 秒内能从照片内的位置到达 $1$ 号草地的牛。

输入格式

第 $1$ 行：四个以空格分隔的整数：$F,P,C$ 和 $M$。

第 $2$ 行至 $P+1$ 行：三个以空格分隔的整数，描述一个路径。连接 $F_1$ 和 $F_2$ 的路径需要 $T$ 秒。

第 $P+2$ 行至 $P+C+1$ 行：每行一个整数，是一头牛的位置。

输出格式

第 $1$ 行输出嫌疑犯的数目，接下来每一行输出一只嫌疑犯的编号，按编号从小到大排序。

样例输入 #1

7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7

样例输出 #1

4
1
2
3
4

数据范围

数据约定

对于 $100\%$ 的数据：$1 \le M \le 7\times 10^4$，$1 \le C \le 100$，$1 \le P \le 1000$，$1 \le F \le 500$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1200。

测试点分布

出处：原题链接