import java.util.Scanner; import java.lang.Math; import java.util.ArrayList; public class TravellingCheap { public static void main(String[] args) { Scanner in = new Scanner(System.in); String assignment = in.nextLine(); if (assignment.trim().equals("Part 1")) { int N = in.nextInt(); // northCost is the minimum cost to get to the northern island previously under consideration int northCost = 0; int southCost = 0; for (int i = 1; i < N; i++) { int northNorthCost = in.nextInt(); int northSouthCost = in.nextInt(); int southNorthCost = in.nextInt(); int southSouthCost = in.nextInt(); int newNorthCost = Math.min(northCost + northNorthCost, southCost + southNorthCost); int newSouthCost = Math.min(northCost + northSouthCost, southCost + southSouthCost); northCost = newNorthCost; southCost = newSouthCost; } int minimum = Math.min(northCost, southCost); System.out.println(minimum); } else if (assignment.trim().equals("Part 2")) { int N = in.nextInt(); int M = in.nextInt(); // board stores the costs of entering cities int[][] board = new int[N][]; for (int i = 0; i < N; i++) { board[i] = new int[M]; for (int j = 0; j < M; j++) { board[i][j] = in.nextInt(); } } int[][] minimumCosts = new int[N][]; minimumCosts[0] = new int[M]; // The first row of cities you can only enter through the entrance for (int j = 0; j < M; j++) { minimumCosts[0][j] = board[0][j]; } for (int i = 1; i < N; i++) { minimumCosts[i] = new int[M]; // This determines the cheapest way to get to a city by foot (so without using the tunnels for this row) // Case 0 is the left side of the board, case M-1 is the right side. minimumCosts[i][0] = Math.min(minimumCosts[i-1][0], minimumCosts[i-1][1]) + board[i][0]; for (int j = 1; j < M - 1; j++) { minimumCosts[i][j] = Math.min(minimumCosts[i-1][j-1], Math.min(minimumCosts[i-1][j], minimumCosts[i-1][j+1])) + board[i][j]; } minimumCosts[i][M - 1] = Math.min(minimumCosts[i-1][M - 2], minimumCosts[i-1][M - 1]) + board[i][M - 1]; // Deal with the tunnels by simply checking whether its better to take a tunnel from a previous city int K = in.nextInt(); for (int c = 0; c < K; c++) { int j = in.nextInt(); int prevX = in.nextInt(); int prevY = in.nextInt(); int cost = in.nextInt(); minimumCosts[i][j] = Math.min(minimumCosts[i][j], minimumCosts[prevX][prevY] + cost); } } // Find the best city to exit int result = minimumCosts[N-1][0]; for (int j = 1; j < M; j++) { result = Math.min(result, minimumCosts[N-1][j]); } System.out.println(result); } else if (assignment.trim().equals("Part 3")) { int N = in.nextInt(); int M = in.nextInt(); int[] rooms = new int[N]; rooms[0] = 0; for (int i = 1; i < N; i++) { // We use -1 as a special value, meaning 'not yet reached' rooms[i] = -1; } ArrayList[] entrances = (ArrayList[]) new ArrayList[N]; ArrayList[] costs = (ArrayList[]) new ArrayList[N]; for (int i = 0; i < N; i++) { entrances[i] = new ArrayList(); costs[i] = new ArrayList(); } // Add all portals to their exits for (int i = 0; i < M; i++) { int entr = in.nextInt(); int exit = in.nextInt(); int cost = in.nextInt(); entrances[exit].add(entr); costs[exit].add(cost); } // For all rooms... for (int i = 0; i < N; i++) { // ...for all portals that exit here... for (int j = 0; j < entrances[i].size(); j++) { int entr = entrances[i].get(j); int cost = costs[i].get(j); // ...if the room is reachable... if (rooms[entr] != -1) { // ...figure out if the portals is a better way of reaching the room if (rooms[i] == -1) { rooms[i] = rooms[entr] + cost; } else { rooms[i] = Math.min(rooms[i], rooms[entr] + cost); } } } } System.out.println(rooms[N-1]); } } }