Rating: -
Tags: -
Solve time: 3m 21s
Verified: yes

Solution

Problem Understanding

The problem describes a subway network where each line is given as an ordered list of stations it visits. The first station is the airport and the target is the hotel. A passenger may ride along a line that contains the current station. Changing from one subway line to another counts as taking another line, while continuing on the same line does not increase the count. The task is to find the smallest number of different subway lines needed to travel from the airport to the hotel.

The useful way to look at the input is not as a graph of stations connected by tracks, because the cost is not the number of stations travelled through. A long ride on one line costs the same as a short ride on that line. The only event that changes the answer is entering a new subway line.

The number of distinct stations is small enough that a graph search over the subway network is practical. If there were hundreds of thousands of stations or lines, we would need more careful preprocessing, but here the total number of station occurrences in the input is limited, so building explicit relationships between lines and transfer stations is feasible. A quadratic search over all possible station paths would still be wasteful because the passenger does not care about intermediate stations inside a line.

The tricky cases are situations where several lines share a station or where the start and destination are on the same line. For example:

3
Airport A Hotel
A B C
C Hotel

The correct answer is 1, because the first line already connects the two required stations. A careless solution that counts stations visited instead of line changes would produce a larger answer.

Another case is when a transfer is required immediately:

2
Airport X
X Hotel

The correct answer is 2. The passenger must first take the line containing Airport, then change to the line containing Hotel at station X.

A third case is multiple transfers through the same station:

3
Airport A
A B
B Hotel

The answer is 3. Treating stations as the main graph and forgetting that every line change has a cost can underestimate the answer.

Approaches

A straightforward approach is to search through possible station paths. Starting from the airport, we could repeatedly try every station reachable by the current subway line and keep track of how many lines have been used. This is correct because every possible journey is considered, but it explores many equivalent paths. Riding from one station to another on the same line creates many unnecessary states.

The key observation is that the exact station inside a line does not matter while the passenger stays on that line. The meaningful state is the current subway line. If we know that we are currently using line X, we can immediately reach every station served by line X without paying another line. From any station on line X, we may switch to every other line passing through that station, paying one additional line.

This transforms the problem into a shortest path problem on subway lines. Each node represents a subway line. An edge exists between two lines if they share at least one station. The edge cost is one because moving from one line to another adds exactly one line to the journey. The starting nodes are all lines containing the airport, with initial cost one. A breadth-first search then finds the minimum number of lines needed to reach any line containing the hotel.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force over station paths	Exponential in the number of choices	O(number of states)	Too slow
BFS over subway lines	O(total station occurrences + transfers)	O(number of lines + stations)	Accepted

Algorithm Walkthrough

Read every subway line and store the stations that belong to it. At the same time, build a mapping from each station to the list of subway lines that visit it. This reverse mapping is the important structure because transfers happen at stations.
Find all subway lines containing the airport. Put these lines into a BFS queue with distance one. Starting with distance one represents the fact that using any subway line already counts as taking one line.
Pop a subway line from the queue. For every station on this line, inspect every other subway line passing through that station. If such a line has not been visited, assign it a distance one larger and add it to the queue.
Whenever a visited line contains the hotel station, the stored distance is the minimum number of subway lines needed.

Why it works:

BFS explores states in increasing order of the number of subway lines used. Moving inside a line costs nothing extra, so all stations on a line are handled together. Every possible transfer is represented by an edge between two lines. Since BFS finds the shortest path in an unweighted graph, the first time we reach a hotel line we have found the minimum possible number of lines.

Python Solution

import sys
from collections import deque, defaultdict

input = sys.stdin.readline

def solve():
    n = int(input())
    
    lines = []
    station_to_lines = defaultdict(list)
    
    for i in range(n):
        stations = input().split()
        lines.append(stations)
        for s in stations:
            station_to_lines[s].append(i)

    start = "Airport"
    target = "Hotel"

    dist = [-1] * n
    q = deque()

    for line in station_to_lines[start]:
        dist[line] = 1
        q.append(line)

    answer = -1

    while q:
        line = q.popleft()

        if target in lines[line]:
            answer = dist[line]
            break

        for station in lines[line]:
            for nxt in station_to_lines[station]:
                if dist[nxt] == -1:
                    dist[nxt] = dist[line] + 1
                    q.append(nxt)

    print(answer)

if __name__ == "__main__":
    solve()

The list station_to_lines is the reverse index of the subway system. Without it, every transfer would require scanning every line, which would multiply the running time unnecessarily.

The BFS queue stores subway lines rather than stations. This avoids counting movement along a single line as extra cost. The distance array is indexed by line number, and its value is exactly the number of subway lines used to reach that line.

The initialization is a common source of mistakes. The first subway line already contributes one to the answer, so starting distances must be 1, not 0.

The check for the hotel is done when a line is removed from the queue. Since BFS removes states in increasing distance order, the first such line found is optimal.

Worked Examples

For the first sample:

4
Airport CityCenter WestStation
CityCenter Library EastStation
WestStation Countryside
Countryside Library Hotel

The BFS state changes are:

Current line	Distance	Newly reached lines
Airport CityCenter WestStation	1	CityCenter Library EastStation, WestStation Countryside
CityCenter Library EastStation	2	Countryside Library Hotel
WestStation Countryside	2	none
Countryside Library Hotel	3	answer

The result is 3. The trace shows that a transfer is counted only when moving between subway lines.

For the second sample:

5
Airport TownHall
TownHall Courthouse
Courthouse WestStation
WestStation NorthStation
TownHall Hotel

Current line	Distance	Newly reached lines
Airport TownHall	1	TownHall Courthouse, TownHall Hotel
TownHall Hotel	2	answer

The result is 2. The hotel can be reached by transferring once at TownHall.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(S + T)	S is the total number of station appearances in all lines, and T is the number of transfer checks between connected lines
Space	O(S)	The stored line lists and station-to-line mapping contain every station occurrence

The input size is small enough that explicitly storing every station occurrence is safe. BFS visits each subway line once, and every transfer relationship is examined through the station mapping.

Test Cases

import sys
import io
from collections import deque, defaultdict

def run(inp: str) -> str:
    old = sys.stdin
    sys.stdin = io.StringIO(inp)

    n = int(input())
    lines = []
    station_to_lines = defaultdict(list)

    for i in range(n):
        stations = input().split()
        lines.append(stations)
        for s in stations:
            station_to_lines[s].append(i)

    dist = [-1] * n
    q = deque()

    for x in station_to_lines["Airport"]:
        dist[x] = 1
        q.append(x)

    ans = -1
    while q:
        x = q.popleft()
        if "Hotel" in lines[x]:
            ans = dist[x]
            break
        for s in lines[x]:
            for y in station_to_lines[s]:
                if dist[y] == -1:
                    dist[y] = dist[x] + 1
                    q.append(y)

    sys.stdin = old
    return str(ans)

assert run("""1
Airport Hotel
""") == "1"

assert run("""2
Airport X
X Hotel
""") == "2"

assert run("""3
Airport A
A B
B Hotel
""") == "3"

assert run("""4
Airport A B
C D
B C
D Hotel
""") == "3"

Test input	Expected output	What it validates
Single direct line	1	Starting and ending on the same line
Two connected lines	2	Basic transfer handling
Chain of transfers	3	Multiple BFS layers
Several independent lines	3	Correct station-to-line mapping

Edge Cases

When the airport and hotel are on the same subway line, the BFS starts from that line with distance one and immediately returns one. The algorithm never forces an unnecessary transfer.

For:

1
Airport Hotel

the queue initially contains the only line with distance 1. Since that line contains Hotel, the answer is 1.

When a transfer station belongs to many lines, the reverse mapping may contain many candidates. The algorithm checks each candidate once because every line receives a distance only the first time it is discovered.