3482. 我决不会 TLE

单测试点时限: 2.5 秒

内存限制: 256 MB

xxx 写了一份用 DFS 求有向无环图中顶点 最短路的代码,出乎意料的是这份代码竟然通过了所有测试点。于是你暗地里把出题人骂了一通,然后决定造个数据把这个假算法卡掉。

核心代码如下:

global variable: answer_now

function dfs(u, distance_now)
    if distance_now >= answer_now then
        return
    if u == n then 
        answer_now = distance_now
        return
    for each u->v in edges
        dfs(v, dist + 1)

function find_shortest_path()
    answer_now = INFINITY
    dfs(1, 0)
    return answer_now

输出

第一行两个数 ,分别表示图中点的个数和边的条数。
之后 行,每行两个数 ,表示顶点 有一条有向边。

要求:

  • 存在 的路径。
  • 不能有重边。
  • 不能有环。
  • xxx 的算法会给出错误解或者运行超时(时限是 2 秒)。

样例

Input
Sample
Output
7 8
6 7
1 2
1 3
2 4
2 5
3 5
4 6
5 6

提示

样例给出了一种可能的输出(不是正确的输出)。

86 人解决,118 已尝试。

97 份提交通过,共有 376 份提交。

7.1 EMB 奖励。

创建: 10 月,4 周前.

修改: 10 月,3 周前.

最后提交: 2 月,1 周前.

来源: EOJ Monthly 2018.1

标签