2015 Jan Bronze Problem 1 Cow Routing

Problem

The problem gives you three integers A, B and N, representing the starting city, the target city, and the number of flight routes respectively. Each flight route has a cost and a list of cities (in order) that the route will pass. You are asked to determine the minimum cost for Bessie the cow to fly from city A to city B. If there is no such route, output -1.

Solution

This problem can be solved by using a simple greedy approach.

First, we create an array to store the flight cost from each city to the target city B. We initialize this array to infinity since we haven't processed any flight routes yet.

Then we iterate through all flight routes in the input. For each route, we find the first city that is in the route and its cost to the target city is not infinity. This means that we can fly to the target city from this city. Therefore, we can update the flight cost from all cities before this city to the target city (including this city) in this route. The cost should be the larger one between the cost of this flight route and the cost from this city to the target city.

Finally, we output the flight cost from the starting city A to the target city B.

The time complexity of this algorithm is O(n^2), where n is the number of cities. This is because we need to iterate through all cities in each flight route. However, since the constraints of this problem are low (n <= 500), this solution is fast enough.

Code

C++

#include <iostream>
#include <climits> // To use INT_MAX instead of INF

using namespace std;

int main() {
    freopen("cowroute.in", "r", stdin);
    freopen("cowroute.out", "w", stdout);

    int A, B, N; // Declare variables for starting city, target city and number of flight routes
    cin >> A >> B >> N;

    int result = INT_MAX; // Initialize the result with the maximum possible integer value
    for (int i = 0; i < N; i++) { // Loop through each flight route
        int cost, sz; // Declare variables for the cost of the flight route and the number of cities it passes through
        cin >> cost >> sz;

        bool found_A = false; // Variable to check if city A is found in the flight route
        for (int j = 0; j < sz; j++) { // Loop through each city in the flight route
            int city; // Declare a variable for the current city
            cin >> city;

            if (city == A) { // If the current city is city A
                found_A = true; // Set found_A to true
            }

            // If city A is found and the current city is city B
            // Update the result with the minimum cost
            if (found_A && city == B) {
                result = min(result, cost);
            }
        }
    }

    // If no suitable flight route is found, print -1
    // Otherwise, print the minimum cost
    if (result == INT_MAX) {
        cout << "-1\n";
    } else {
        cout << result << '\n';
    }

    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] input = br.readLine().split(" ");
        int A = Integer.parseInt(input[0]); // Starting city
        int B = Integer.parseInt(input[1]); // Target city
        int N = Integer.parseInt(input[2]); // Number of flight routes
        
        int result = Integer.MAX_VALUE; // Initialize the result with the maximum possible integer value

        for (int i = 0; i < N; i++) {
            input = br.readLine().split(" ");
            int cost = Integer.parseInt(input[0]); // Cost of the flight route
            int sz = Integer.parseInt(input[1]); // Number of cities it passes through
            
            boolean found_A = false; // Variable to check if city A is found in the flight route
            input = br.readLine().split(" ");
            
            for (int j = 0; j < sz; j++) { // Loop through each city in the flight route
                int city = Integer.parseInt(input[j]); // Current city

                if (city == A) { // If the current city is city A
                    found_A = true; // Set found_A to true
                }

                // If city A is found and the current city is city B
                // Update the result with the minimum cost
                if (found_A && city == B) {
                    result = Math.min(result, cost);
                }
            }
        }
        
        // If no suitable flight route is found, print -1
        // Otherwise, print the minimum cost
        System.out.println(result == Integer.MAX_VALUE ? "-1" : result);
    }
}

Python

import sys

A, B, N = map(int, input().split())

result = float('inf')  # Initialize the result with the maximum possible integer value

for _ in range(N):
    cost, sz = map(int, input().split())

    found_A = False  # Variable to check if city A is found in the flight route

    cities = list(map(int, input().split()))

    for city in cities:  # Loop through each city in the flight route
        if city == A:  # If the current city is city A
            found_A = True  # Set found_A to true

        # If city A is found and the current city is city B
        # Update the result with the minimum cost
        if found_A and city == B:
            result = min(result, cost)

# If no suitable flight route is found, print -1
# Otherwise, print the minimum cost
if result == float('inf'):
    print("-1")
else:
    print(result)