Swift Coding Test Course, Finding the Fastest Bus Route

Today, we will address the problem of ‘Finding the Fastest Bus Route’ for those of you preparing for coding tests using Swift. This problem requires an understanding of graph exploration, particularly shortest path algorithms. It is a type of problem that frequently appears in actual coding tests, so please pay close attention.

Problem Description

You have information about bus routes in a city. There are N bus stops in this city, and there is a bus route connecting stop i and stop j. Each route has a travel time, that is, a weight assigned to it. Your goal is to find the fastest route from a specific stop S to arrive at stop E. If there is no route, you should output “Cannot arrive.”

Input Format

The first line contains the number of stops N (1 ≤ N ≤ 1000) and the number of bus routes M (1 ≤ M ≤ 1000).
The next M lines contain the stops i, j, and the travel time T for the corresponding bus route.
Finally, two bus stops S and E are given.

Output Format

Please output the fastest travel time or “Cannot arrive.”

Example Input

Example Output

Problem Solving Process

To solve this problem, we will use Dijkstra’s algorithm, which is one of the shortest path algorithms. Dijkstra’s algorithm is useful for finding the shortest path in graphs with weighted edges.

Algorithm Overview

Dijkstra’s algorithm works by using a priority queue to select the next vertex and updating the paths to all vertices connected to that vertex. The shortest distances are gradually expanded through initialization and update processes for all vertices in the graph.

Implementation Steps

Receive Input: Take input for the number of stops N and the number of routes M. Then receive the route information for M routes.
Create Graph Structure: Store the graph in the form of an adjacency list.
Implement Dijkstra’s Algorithm: Calculate the shortest path from the starting stop to all other stops.
Output Result: Output the shortest time to the destination or “Cannot arrive.”

Swift Code Implementation

    import Foundation

    struct BusRoute {
        let destination: Int
        let time: Int
    }

    func dijkstra(n: Int, graph: [[BusRoute]], start: Int, end: Int) -> Int {
        var distances = Array(repeating: Int.max, count: n + 1)
        var priorityQueue = [(Int, Int)]()  // (stop, time)
        distances[start] = 0
        priorityQueue.append((start, 0))
        
        while !priorityQueue.isEmpty {
            priorityQueue.sort { $0.1 < $1.1 }
            let (current, currentDistance) = priorityQueue.removeFirst()

            if currentDistance > distances[current] {
                continue
            }

            for route in graph[current] {
                let newDistance = currentDistance + route.time
                if newDistance < distances[route.destination] {
                    distances[route.destination] = newDistance
                    priorityQueue.append((route.destination, newDistance))
                }
            }
        }

        return distances[end] == Int.max ? -1 : distances[end]
    }

    func main() {
        let input = readLine()!.split(separator: " ").map { Int($0)! }
        let n = input[0]
        let m = input[1]
        var graph = Array(repeating: [BusRoute](), count: n + 1)

        for _ in 0..
Code Explanation

        The above code implements Dijkstra's algorithm. After constructing the graph based on input, it calculates the shortest path from the given starting point and outputs the result. Using a priority queue to find the fastest route is key.
    
Conclusion

        I hope this problem has enhanced your understanding of shortest path problems, which frequently appear in coding tests. You can solve various problems using Dijkstra's algorithm as well as other graph algorithms. I encourage you to become a developer equipped with both theory and practical skills through continuous practice.