#P1811. 最短路
最短路
题目描述
给定一个包含 个点, 条边的无向图,每条边的边权均为 。
再给定 个三元组 ,表示从 点走到 点后不能往 点走。注意三元组是有序的,如可以从 点走到 点再走到 。
现在你要在 个三元组的限制下,找出 号点到 号点的最短路径,并输出任意一条合法路径,会有 Check 检查你的输出。
输入格式
输入文件第一行有三个数 ,,,意义如题目所述。
接下来 行每行两个数 ,,表示 , 间有一条边。
再下面 行,每行三个数 描述一个三元组。
输出格式
输出文件共两行数,第一行一个数 表示最短路径长度。 。
第二行 个数,表示从 到 所经过的节点。 。
4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4
4
1 3 2 3 4
提示
对于 的数据满足 ,,。
对于 的数据满足 ,,。