华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 971|回复: 0
打印 上一主题 下一主题

P1811 最短路

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-5-17 12:55:16 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
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。

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 02:40 , Processed in 0.373153 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表