华师一附中OI组

标题: P1811 最短路 [打印本页]

作者: admin 时间: 2018-5-17 12:55
标题: P1811 最短路
https://www.luogu.org/problemnew/show/P1811

题目描述
给定一个包含N个点，M条边的无向图，每条边的边权均为1。

再给定K个三元组（A，B，C），表示从A点走到B点后不能往C点走。注意三元组是有序的，如可以从B点走到A点再走到C。

现在你要在K个三元组的限制下，找出1号点到N号点的最短路径，并输出任意一条合法路径，会有Check检查你的输出。

输入输出格式
输入格式：
输入文件第一行有三个数N，M，K，意义如题目所述。

接下来M行每行两个数A，B，表示A，B间有一条边。

再下面K行，每行三个数（A，B，C）描述一个三元组。

输出格式：
输出文件共两行数，第一行一个数S表示最短路径长度。

第二行S+1个数，表示从1到N所经过的节点。

输入输出样例
输入样例#1：
4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4
输出样例#1：
4
1 3 2 3 4
说明
对于40%的数据满足N≤10，M≤20，K≤5。

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

欢迎光临华师一附中OI组 (http://hsyit.cn/)