National Olympiad in Informatics, China, 1997
Day 1, Problem 2 - Optimal Routing
City H is a popular tourist attraction with thousands of visitors every year. For the convenience of tourists, a bus company has established N bus stops (labeled from 1 to N) and M one-way routes around locations like hotels and restaurants. Each one-way route starts at some initial bus stop, passes through some number of other stops, and terminates at a final bus stop.
A tourist has arrived at city H, and is currently at a restaurant near bus stop 1. He really wants to visit park S near bus stop N. However if from his current location there is no single bus route that can take him to the park, he might have to take a bus for one or more stops, get off, transfer to another bus passing through the stop at which he got off, and repeat several times until he finally reaches his destination.
Write a program to help this tourist find an optimal bus route from the restaurant to the park, such that the number of transfers during his route is as small as possible.
The first line of input contains two integers M and N (1 ≤ M ≤ 100, 1 < N ≤ 500), indicating the number of one-way bus routes and the number of bus stops that the company built. The (i+1)-th line of input describes the i-th bus route (for 1 ≤ i ≤ M). Each of these lines will have some number of space-separated integers from 1 to N, indicating the stops numbers that the route passes through in the order that they are given.
The output should contain one line - the minimum number of transfers that the tourist is required to make to get to park S, or a single line with the string "
NO" (without quotes) if it is is not possible to reach the park from the restaurant. Note that if the number of transfers is 0, the tourist can directly reach the park without making any transfers.
3 7 6 7 4 7 3 6 2 1 3 5
Point Value: 12 (partial)
Time Limit: 1.00s
Memory Limit: 16M
Added: Apr 27, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3