| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 15 | 7 | 7 | 63.636% |
As you are probably aware, flight pricing can sometimes be surprisingly complex. For example, it can often be cheaper to take a much longer flight with several legs instead of flying directly between two airports. One of the reasons pricing seems to be complex is that airlines often try to obfuscate exactly how pricing works, in order to ensure that their customers choose more expensive flights.
One particular airline has decided to take this obfuscation to the next level; they do not even offer an automated search of their flights. Instead, they describe their flights in a very peculiar format. For every one of their $N$ airports (which are numbered between 0ドル$ and $N - 1$), they list either:
To compensate for this complexity, the airline sets the price of every direct flight between two airports to the same amount.
Can you write a program that, given the descriptions of all the flights the airline provides, determine the minimum number of flights required to travel from airport $s$ to airport $t$?
The first line of input contains an integer 1ドル \le N \le 10^5,ドル the number of airports, and the two integers $s$ and $t$ (0ドル \le s, t < N,ドル $s \neq t$).
The next $N$ lines each describe the outgoing flights of an airport, starting with airport 0ドル$. The line starts with a letter. If this letter is N, you will get a list of all destination airports from this airport. If this letter is C, you will get a list of all airports that are not destinations from this airport.
Following this letter is an integer $m,ドル the number of airports in the list. Finally, there will $m$ unique numbers $a_i$ (0ドル \le a_i < N$) on the line, the airports in the list.
The sum of $m$ over all airports is at most 2ドル \cdot 10^5$.
Output a single integer, the minimum number of flights required to travel from airport $s$ to airport $t$.
If there is no path, output "impossible".
4 0 1 N 1 2 C 1 2 N 1 3 C 1 1
impossible
The only flight from airport 0ドル$ is to airport 2ドル$. From airport 2ドル,ドル there is also only a single flight going to airport 3ドル$. From airport 3ドル,ドル you can fly to any airport except airport 1ドル$.
Since no airport has a direct flight to airport 1ドル,ドル there cannot be any possible flight plan from airport 0ドル$ to 1ドル,ドル so the answer is impossible.
4 0 1 N 1 2 C 1 2 N 1 3 C 1 0
3
The only flight from airport 0ドル$ is to airport 2ドル$. From airport 2ドル,ドル there is also only a single flight going to airport 3ドル$. From airport 3ドル,ドル you can fly to any airport except airport 0ドル$.
Thus, there is a flight plan from 0ドル$ to 1ドル$ going from 0ドル$ to 2ドル,ドル to 3ドル,ドル to 1ドル,ドル which results in 3 flights. This is also the shortest flight plan.