P1811 最短路_NOI导刊2011提高(01)

    • 62通过
    • 215提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 NOI导刊
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一个包含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。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。