2015 Jan Bronze Problem 2 Cow Routing II

Official Problem Statement

Cow Routing II

Problem

Bessie the cow has been given a task to transport goods from city A to city B. She can use multiple flights to complete this task, and each flight covers multiple cities in sequence and has a certain cost. However, the cost of the flight does not change regardless of where Bessie boards or disembarks. Bessie is looking for the cheapest way to reach city B from city A, and in case of multiple cheapest routes, Bessie wants to choose the one with the smallest number of flights. The task is to write a program to help Bessie find such a route.

Input:

• The first line contains three integers: A, B and N, representing the starting city, target city and number of flights respectively (1 ≤ A, B ≤ N ≤ 1000).
• The next N lines each describe a flight route. Each line begins with two integers C and M, indicating the cost of the flight and the number of cities it passes through, followed by M integers indicating the cities it covers in order.

Output:

• If Bessie can reach city B from city A, output two integers: the minimum total cost of the flights and the minimum number of flights. If Bessie cannot reach city B from city A, output "-1 -1".

Solution

The problem can be solved by Dijkstra's shortest path algorithm on a directed graph where each city is a node, each flight is a directed edge from every city in its route to every later city in its route, the weight of the edge is the cost of the flight, and if multiple edges connect the same two nodes, keep only the one with the minimum weight. A modification of the algorithm is needed to count the number of flights. Initialize the shortest path to every node as infinity and then run the modified Dijkstra's algorithm to find the shortest path from city A to every other city. Finally, return the shortest path and the minimum number of flights from city A to city B.

Pseudocode:

• Initialize a 2D array dist[N][N] where N is the number of flights, and fill it with infinity.
• For each flight, for each pair of cities (i, j) such that city i comes before city j in the route, update dist[i][j] to be the minimum between the old dist[i][j] and the cost of the flight.
• Initialize a 2D array dp[N][N] to store the shortest path and the minimum number of flights from city A to each other city, and fill it with infinity for the path and 0 for the flights.
• Set dp[A][0] to be 0 for the path and 0 for the flights.
• For each city i from 1 to N - 1, for each city u, if dp[u][i - 1] is less than infinity, for each city v, if dist[u][v] is less than infinity, update dp[v][i] to be the minimum between the old dp[v][i] and dp[u][i - 1] + dist[u][v] for the path and i for the flights.
• Find the minimum path and the corresponding flights from dp[B][0] to dp[B][N - 1] and return them. If the minimum path is infinity, return "-1 -1".

Code

C++

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

const int INF = 1e6;
const int MAX_NODES = 10000;

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

    int A, B, N;
    cin >> A >> B >> N;

    vector<int> costs(N);
    vector<vector<int>> routes(N);

    for (int i = 0; i < N; i++) {
        int route_len;
        cin >> costs[i] >> route_len;
        routes[i].resize(route_len);
        for (int j = 0; j < route_len; j++) {
            cin >> routes[i][j];
        }
    }

    vector<int> cost_to_B(MAX_NODES + 1, INF), cost_to_A(MAX_NODES + 1, INF);

    cost_to_A[A] = 0;
    cost_to_B[B] = 0;

    for (int i = 0; i < N; i++) {
        int cost = costs[i];
        vector<int>& route = routes[i];

        int pos_A = route.size(), pos_B = -1;
        for (int j = 0; j < route.size(); j++) {
            if (route[j] == A) pos_A = j;
            if (route[j] == B) pos_B = j;
        }

        for (int j = 0; j < route.size(); j++) {
            if (j >= pos_A) cost_to_A[route[j]] = min(cost_to_A[route[j]], cost);
            if (j <= pos_B) cost_to_B[route[j]] = min(cost_to_B[route[j]], cost);
        }
    }

    int result = INF;
    for (int i = 1; i <= MAX_NODES; i++) {
        result = min(result, cost_to_A[i] + cost_to_B[i]);
    }

    cout << (result == INF ? -1 : result) << endl;

    return 0;
}

Java

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

public class CowRouting {
    private static final int INF = (int) 1e6;
    private static final int MAX_NODES = 10000;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StringTokenizer st = new StringTokenizer(reader.readLine());

        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        List<Integer> costs = new ArrayList<>();
        List<List<Integer>> routes = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(reader.readLine());
            int cost = Integer.parseInt(st.nextToken());
            int route_len = Integer.parseInt(st.nextToken());
            costs.add(cost);

            List<Integer> route = new ArrayList<>();
            st = new StringTokenizer(reader.readLine());
            for (int j = 0; j < route_len; j++) {
                route.add(Integer.parseInt(st.nextToken()));
            }
            routes.add(route);
        }

        int[] cost_to_A = new int[MAX_NODES + 1];
        int[] cost_to_B = new int[MAX_NODES + 1];

        Arrays.fill(cost_to_A, INF);
        Arrays.fill(cost_to_B, INF);

        cost_to_A[A] = 0;
        cost_to_B[B] = 0;

        for (int i = 0; i < N; i++) {
            int cost = costs.get(i);
            List<Integer> route = routes.get(i);

            int pos_A = route.size(), pos_B = -1;
            for (int j = 0; j < route.size(); j++) {
                if (route.get(j) == A) pos_A = j;
                if (route.get(j) == B) pos_B = j;
            }

            for (int j = 0; j < route.size(); j++) {
                if (j >= pos_A) cost_to_A[route.get(j)] = Math.min(cost_to_A[route.get(j)], cost);
                if (j <= pos_B) cost_to_B[route.get(j)] = Math.min(cost_to_B[route.get(j)], cost);
            }
        }

        int result = INF;
        for (int i = 1; i <= MAX_NODES; i++) {
            result = Math.min(result, cost_to_A[i] + cost_to_B[i]);
        }

        writer.println(result == INF ? -1 : result);
        writer.close();
    }
}

Python

import sys

INF = int(1e6)
MAX_NODES = 10000

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

    costs = []
    routes = []
    for _ in range(N):
        cost, route_len = map(int, input().split())
        route = list(map(int, input().split()))
        costs.append(cost)
        routes.append(route)

    cost_to_A = [INF]*(MAX_NODES + 1)
    cost_to_B = [INF]*(MAX_NODES + 1)
    cost_to_A[A] = 0
    cost_to_B[B] = 0

    for i in range(N):
        cost = costs[i]
        route = routes[i]
        pos_A = len(route)
        pos_B = -1

        for j in range(len(route)):
            if route[j] == A:
                pos_A = j
            if route[j] == B:
                pos_B = j

        for j in range(len(route)):
            if j >= pos_A:
                cost_to_A[route[j]] = min(cost_to_A[route[j]], cost)
            if j <= pos_B:
                cost_to_B[route[j]] = min(cost_to_B[route[j]], cost)

    result = INF
    for i in range(1, MAX_NODES + 1):
        result = min(result, cost_to_A[i] + cost_to_B[i])

    print(-1 if result == INF else result)

if __name__ == "__main__":
    main()