AT_abc481_d.Autopilot

普及-

通过率:0%

时间限制:2.00s

内存限制:1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

There are NN planets and MM routes. The planets are numbered 11 to NN, and the routes are numbered 11 to MM.

Route ii goes from planet AiA_i to planet BiB_i. Each route is one-way.

A spaceship can perform the following two types of operations.

  • Move, without consuming fuel, to the planet with the smallest number among the planets directly reachable by a route from the current planet.
  • Choose any planet directly reachable by a route from the current planet, and move to the chosen planet, consuming 11 unit of fuel.

Find the minimum amount of fuel the spaceship consumes to start from planet SS and arrive at planet TT. If it is impossible to reach planet TT, print −1-1 instead.

共有 NN 颗行星和 MM 条航线。行星编号为 11 至 NN,航线编号为 11 至 MM。

第 ii 条航线从行星 AiA_i 单向通往行星 BiB_i。

一艘宇宙飞船可执行以下两类操作:

  • 不消耗燃料地移动至当前行星通过某条航线可直接到达的行星中编号最小者;
  • 任选一个当前行星通过某条航线可直接到达的行星,并移动至该行星,消耗 11 单位燃料。

求飞船从行星 SS 出发、抵达行星 TT 所需消耗的最少燃料量。若无法抵达行星 TT,则输出 −1-1。

输入格式

The input is given from Standard Input in the following format:

NN MM SS TT
A1A_1 B1B_1
⋮\vdots
AMA_M BMB_M

输入从标准输入中按以下格式给出:

NN MM SS TT
A1A_1 B1B_1
⋮\vdots
AMA_M BMB_M

输出格式

Print the answer.

输出答案。

输入输出样例

  • 输入#1

    7 10 2 1
    2 5
    2 4
    4 2
    4 3
    3 1
    3 5
    3 6
    5 6
    6 1
    6 7

    输出#1

    1
  • 输入#2

    7 10 2 7
    2 5
    2 4
    4 2
    4 3
    3 1
    3 5
    3 6
    5 6
    6 1
    6 7

    输出#2

    2
  • 输入#3

    2 1 1 2
    2 1

    输出#3

    -1

说明/提示

Sample 1 Explanation:
By moving in the following order, the spaceship can travel from planet 22 to planet 11 with a fuel consumption of 11.

  1. Move from planet 22 to planet 44 without consuming fuel.
  2. Move from planet 44 to planet 33, consuming 11 unit of fuel.
  3. Move from planet 33 to planet 11 without consuming fuel.

Sample 2 Explanation:
By moving in the following order, the spaceship can travel from planet 22 to planet 77 with a fuel consumption of 22.

  1. Move from planet 22 to planet 44 without consuming fuel.
  2. Move from planet 44 to planet 22 without consuming fuel.
  3. Move from planet 22 to planet 55, consuming 11 unit of fuel.
  4. Move from planet 55 to planet 66 without consuming fuel.
  5. Move from planet 66 to planet 77, consuming 11 unit of fuel.

Sample 3 Explanation:
It is impossible to start from planet 11 and reach planet 22.

Constraints

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤S,T≤N1 \leq S,T \leq N
  • S≠TS \neq T
  • 1≤Ai,Bi≤N1 \leq A_i, B_i \leq N
  • Ai≠BiA_i \neq B_i
  • All input values are integers.

样例 1 解释:
按照以下顺序移动,飞船可以从行星 22 到达行星 11,且总耗油量为 11。

  1. 从行星 22 移动到行星 44,不消耗燃料。
  2. 从行星 44 移动到行星 33,消耗 11 单位燃料。
  3. 从行星 33 移动到行星 11,不消耗燃料。

样例 2 解释:
按照以下顺序移动,飞船可以从行星 22 到达行星 77,且总耗油量为 22。

  1. 从行星 22 移动到行星 44,不消耗燃料。
  2. 从行星 44 移动到行星 22,不消耗燃料。
  3. 从行星 22 移动到行星 55,消耗 11 单位燃料。
  4. 从行星 55 移动到行星 66,不消耗燃料。
  5. 从行星 66 移动到行星 77,消耗 11 单位燃料。

样例 3 解释:
无法从行星 11 出发到达行星 22。

约束条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 1≤S,T≤N1 \leq S,T \leq N
  • S≠TS \neq T
  • 1≤Ai,Bi≤N1 \leq A_i, B_i \leq N
  • Ai≠BiA_i \neq B_i
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页