首页 / 题库

P70028 - 道路规划(road)

基础算法
通过次数0 提交次数44 内存限制 512MB 时间限制1秒

描述

小A所在的岛上一共有 n 座城市,城市之间一共有 m 条单向道路连接,保证这些道路不会形成环路,也就是不存在从某座城市出发,经过一系列的道路最终又回到原点的情况。

出于某种原因,小A需要从起点城市 s 前往城市 t,可能会有许多种不同的路径。小A想知道途径的可能的城市(除s、 t外)中,哪一个城市对他是最重要的,换句话说,从 s 到 t 的所有路径中,需要经过哪个城市的路径条数最多。

 

给定一个 n 个点 m 条边的有向无环图,所有点的编号从  到 n,给出一个起点 s 和一个终点 t,求出一个点 ans,使得经过 ans 的从 s 到 t 的路径最多。

输出这个点 ans 和具体的路径数,如果有多个点经过的数量相同,取编号最小的那一个;如果 s 不能到达 t,或从 s 到 t 的路径中间不能途径其他点,输出 -1。

输入

从文件road.in中读入数据。

    输入的第一行包含 4 个整数,分别为 n,m,s,t,表示点数、边数、起点和终点。

    接下来 m 行,每行 2 个整数 u、v,表示存在一条从 u 到 v 的有向路径。

输出

输出到文件road.out中。

       输出仅1 行。如果 s 不可达 t,或中间不能途径其他点,输出 -1;否则输出两个数字,表示最重要的点的编号和经过它的路径条数。

样例

  • 复制
  • 复制

提示

样例图如下,起点是1,终点是5:

经过2 的路径最多,一共有 4条:{1,2,3,5},{1,2,4,5},{1,2,5},{1,2,3,4,5}。经过3的路径也有4条{1,2,3,5},{1,3,5},{1,3,4,5},{1,2,3,4,5},但是2的编号更小。

意见反馈

    最多上传3张图片,格式为JPG、PNG、JPEG,单张不超过5MB

    注册

    发送验证码

    密码必须包含数字、字母和特殊字符

    找回密码

    发送验证码

    密码必须包含数字、字母和特殊字符

    运行 ID:67149

    • 测试点1:Accepted
    • 用时:0 ms
    • 内存:288 kb
    • 测试点2:Accepted
    • 用时:0 ms
    • 内存:288 kb
    输入
    203
    输出
    203

    test

    测评信息

    错误.in文件下载

    错误.out文件下载

    运行 ID:67149

    2019-01-24 15:06:36