AT_abc481_d.Autopilot
普及-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There are N planets and M routes. The planets are numbered 1 to N, and the routes are numbered 1 to M.
Route i goes from planet Ai to planet Bi. 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 1 unit of fuel.
Find the minimum amount of fuel the spaceship consumes to start from planet S and arrive at planet T. If it is impossible to reach planet T, print −1 instead.
共有 N 颗行星和 M 条航线。行星编号为 1 至 N,航线编号为 1 至 M。
第 i 条航线从行星 Ai 单向通往行星 Bi。
一艘宇宙飞船可执行以下两类操作:
- 不消耗燃料地移动至当前行星通过某条航线可直接到达的行星中编号最小者;
- 任选一个当前行星通过某条航线可直接到达的行星,并移动至该行星,消耗 1 单位燃料。
求飞船从行星 S 出发、抵达行星 T 所需消耗的最少燃料量。若无法抵达行星 T,则输出 −1。
输入格式
The input is given from Standard Input in the following format:
N M S T
A1 B1
⋮
AM BM
输入从标准输入中按以下格式给出:
N M S T
A1 B1
⋮
AM BM
输出格式
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 2 to planet 1 with a fuel consumption of 1.
- Move from planet 2 to planet 4 without consuming fuel.
- Move from planet 4 to planet 3, consuming 1 unit of fuel.
- Move from planet 3 to planet 1 without consuming fuel.
Sample 2 Explanation:
By moving in the following order, the spaceship can travel from planet 2 to planet 7 with a fuel consumption of 2.
- Move from planet 2 to planet 4 without consuming fuel.
- Move from planet 4 to planet 2 without consuming fuel.
- Move from planet 2 to planet 5, consuming 1 unit of fuel.
- Move from planet 5 to planet 6 without consuming fuel.
- Move from planet 6 to planet 7, consuming 1 unit of fuel.
Sample 3 Explanation:
It is impossible to start from planet 1 and reach planet 2.
Constraints
- 2≤N≤2×105
- 1≤M≤2×105
- 1≤S,T≤N
- S=T
- 1≤Ai,Bi≤N
- Ai=Bi
- All input values are integers.
样例 1 解释:
按照以下顺序移动,飞船可以从行星 2 到达行星 1,且总耗油量为 1。
- 从行星 2 移动到行星 4,不消耗燃料。
- 从行星 4 移动到行星 3,消耗 1 单位燃料。
- 从行星 3 移动到行星 1,不消耗燃料。
样例 2 解释:
按照以下顺序移动,飞船可以从行星 2 到达行星 7,且总耗油量为 2。
- 从行星 2 移动到行星 4,不消耗燃料。
- 从行星 4 移动到行星 2,不消耗燃料。
- 从行星 2 移动到行星 5,消耗 1 单位燃料。
- 从行星 5 移动到行星 6,不消耗燃料。
- 从行星 6 移动到行星 7,消耗 1 单位燃料。
样例 3 解释:
无法从行星 1 出发到达行星 2。
约束条件
- 2≤N≤2×105
- 1≤M≤2×105
- 1≤S,T≤N
- S=T
- 1≤Ai,Bi≤N
- Ai=Bi
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?