← 返回 google 的题目列表Minimum Direction Violations
类型：online_judge
Minimum Direction Violations
You are given a directed graph with n nodes labeled from 0 to n - 1. edges[i] = [u, v] represents an original directed edge u -> v.
Every edge may actually be traversed in either direction:
Traveling from u to v, along the original direction, costs 0.
Traveling from v to u, against the original direction, costs 1.
Given a starting node start and a destination node end, return the minimum number of times you must travel against an original edge direction in order to reach end from start.
Return -1 if end is unreachable from start.
Example 1
Input:
n = 5
edges = [[0, 1], [2, 1], [2, 3], [4, 3]]
start = 0
end = 4
Output: 2
Explanation:
One valid path is 0 -> 1 -> 2 -> 3 -> 4.
Its edge costs are 0, 1, 0, and 1, for a total cost of 2.
Example 2
Input:
n = 4
edges = [[0, 1], [1, 2], [2, 3]]
start = 0
end = 3
Output: 0
Example 3
Input:
n = 3
edges = [[0, 1], [1, 2]]
start = 2
end = 0
Output: 2
Constraints
1 <= n <= 2 * 10^5
0 <= edges.length <= 2 * 10^5
edges[i].length == 2
0 <= u, v < n
0 <= start, end < n
u != v
The graph may contain parallel edges and cycles.
Example
Input
5 4
0 1
2 1
2 3
4 3
0 4
Output
2