三元限制最短路

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 patha.in 输出文件 patha.out

【题目描述】

给定一个包含 N 个点，M 条边的无向图，每条边的边权均为 1。 再给定 K 个三元组（A，B，C） ，表示从 A 点走到 B 点后不能往 C 点走。注意三元组是有序的，如可 以从 B 点走到 A 点再走到 C。 现在你要在 K 个三元组的限制下，找出 1 号点到 N 号点的最短路径，并输出任意一条合法路径，会有 spj (Special Judge) 检查你的输出。

【输人格式】

    输入文件第一行有三个数 N，M，K，意义如题目所述。 接下来 M 行每行两个数 A，B，表示 A，B 间有一条边。 再下面 K 行，每行三个数（A，B，C）描述一个三元组。

【输出格式】

输出文件共两行数，第一行一个数 S 表示最短路径长度。 第二行 S+1 个数，表示从 1 到 N 所经过的节点。

【输入样例】

4 4 2 

1 2

2 3

3 4 

1 3 

1 2 3 

1 3 4

【输出样例】

4

1 3 2 3 4

【数据规模】

对于 40%的数据满足 N≤10，M≤20，K≤5。 

对于 100%的数据满足 N≤3000，M≤20000，K≤100000。