2015 Jan Bronze Problem 4 Meeting Time

Official Problem Statement

Meeting Time

Problem

Given the topology of a network of N (1 ≤ N ≤ 16) pastures connected by M (1 ≤ M ≤ N(N-1)/2) bidirectional trails. Each trail takes a certain amount of time to traverse. Bessie and her sister Elsie both plan to attend a meeting scheduled at a particular pasture, and they leave simultaneously from their own respective pastures.

We need to find the earliest possible meeting time for Bessie and Elsie. The meeting time is defined as the maximum of the times when Bessie and Elsie arrive at the meeting pasture. If there is no way for the cows to meet, print "IMPOSSIBLE". It is guaranteed that each trail can be traversed in less than 100 minutes, and that the total sum of all the trail lengths is less than 1,000,000,000.

Solution

We solve this problem by calculating the shortest times from each pasture to the meeting pasture for both Bessie and Elsie. Then, for each pair of starting pastures, we calculate the meeting time by taking the maximum of the two times, and we keep track of the minimum meeting time across all pairs of starting pastures.

For calculating the shortest times, we can use the Floyd-Warshall algorithm. The Floyd-Warshall algorithm works by repeatedly iterating over all pairs of nodes and attempting to improve the shortest path between them by including a third node.

Finally, after we have calculated the shortest times for both Bessie and Elsie, we iterate over all pairs of starting pastures and calculate the meeting time. The meeting time is simply the maximum of the two times, since they leave simultaneously and the meeting cannot start until both have arrived. We keep track of the minimum meeting time across all pairs of starting pastures, and this is our answer.

Code

C++

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAX_TIME = 20000;
int pastureCount;
vector<vector<int>> bessieGrid, elsieGrid;
bool bessieCan[MAX_TIME], elsieCan[MAX_TIME];

void calculateRoutes(vector<vector<int>>& grid, bool canArrive[], int currentPasture, int currentTime) {
    if (currentPasture == pastureCount - 1) {
        canArrive[currentTime] = true;
        return;
    }
    for (int nextPasture = currentPasture + 1; nextPasture < pastureCount; nextPasture++) {
        if (grid[currentPasture][nextPasture] > 0) {
            calculateRoutes(grid, canArrive, nextPasture, currentTime + grid[currentPasture][nextPasture]);
        }
    }
}

int main() {
    cin >> pastureCount;
    int trailCount;
    cin >> trailCount;

    bessieGrid.resize(pastureCount, vector<int>(pastureCount));
    elsieGrid.resize(pastureCount, vector<int>(pastureCount));
    memset(bessieCan, false, sizeof(bessieCan));
    memset(elsieCan, false, sizeof(elsieCan));

    for (int i = 0; i < trailCount; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        cin >> bessieGrid[x][y];
        cin >> elsieGrid[x][y];
    }

    calculateRoutes(bessieGrid, bessieCan, 0, 0);
    calculateRoutes(elsieGrid, elsieCan, 0, 0);

    int earliestMeetingTime = MAX_TIME;
    for (int i = 0; i < MAX_TIME; i++) {
        if (bessieCan[i] && elsieCan[i]) {
            earliestMeetingTime = i;
            break;
        }
    }

    if (earliestMeetingTime == MAX_TIME) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        cout << earliestMeetingTime << endl;
    }

    return 0;
}

Java

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

public class Meeting {
    private static final int MAX_TIME = 20000;
    private static int[][] bessieGrid, elsieGrid;
    private static boolean[] bessieCan, elsieCan;
    private static int pastureCount;

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

        pastureCount = Integer.parseInt(tokenizer.nextToken());
        int trailCount = Integer.parseInt(tokenizer.nextToken());
        
        bessieGrid = new int[pastureCount][pastureCount];
        elsieGrid = new int[pastureCount][pastureCount];

        for (int i = 0; i < trailCount; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(tokenizer.nextToken()) - 1;
            int y = Integer.parseInt(tokenizer.nextToken()) - 1;
            bessieGrid[x][y] = Integer.parseInt(tokenizer.nextToken());
            elsieGrid[x][y] = Integer.parseInt(tokenizer.nextToken());
        }

        bessieCan = new boolean[MAX_TIME];
        elsieCan = new boolean[MAX_TIME];

        calculateRoutes(bessieGrid, bessieCan, 0, 0);
        calculateRoutes(elsieGrid, elsieCan, 0, 0);

        int earliestMeetingTime = Integer.MAX_VALUE;
        for (int i = 0; i < MAX_TIME; i++) {
            if (bessieCan[i] && elsieCan[i]) {
                earliestMeetingTime = i;
                break;
            }
        }

        if (earliestMeetingTime == Integer.MAX_VALUE) {
            writer.println("IMPOSSIBLE");
        } else {
            writer.println(earliestMeetingTime);
        }
    }

    public static void calculateRoutes(int[][] grid, boolean[] canArrive, int currentPasture, int currentTime) {
        if (currentPasture == pastureCount - 1) {
            canArrive[currentTime] = true;
            return;
        }
        for (int nextPasture = currentPasture + 1; nextPasture < pastureCount; nextPasture++) {
            if (grid[currentPasture][nextPasture] > 0) {
                calculateRoutes(grid, canArrive, nextPasture, currentTime + grid[currentPasture][nextPasture]);
            }
        }
    }
}

Python

import sys

MAX_TIME = 20000
pastureCount = 0
bessieGrid = []
elsieGrid = []
bessieCan = [False for _ in range(MAX_TIME)]
elsieCan = [False for _ in range(MAX_TIME)]

def calculateRoutes(grid, canArrive, currentPasture, currentTime):
    if currentPasture == pastureCount - 1:
        canArrive[currentTime] = True
        return
    for nextPasture in range(currentPasture + 1, pastureCount):
        if grid[currentPasture][nextPasture] > 0:
            calculateRoutes(grid, canArrive, nextPasture, currentTime + grid[currentPasture][nextPasture])

def main():
    global pastureCount, bessieGrid, elsieGrid, bessieCan, elsieCan
    pastureCount, trailCount = map(int, sys.stdin.readline().split())
    
    bessieGrid = [[0 for _ in range(pastureCount)] for _ in range(pastureCount)]
    elsieGrid = [[0 for _ in range(pastureCount)] for _ in range(pastureCount)]

    for _ in range(trailCount):
        x, y, bessieTime, elsieTime = map(int, sys.stdin.readline().split())
        x -= 1
        y -= 1
        bessieGrid[x][y] = bessieTime
        elsieGrid[x][y] = elsieTime

    calculateRoutes(bessieGrid, bessieCan, 0, 0)
    calculateRoutes(elsieGrid, elsieCan, 0, 0)

    earliestMeetingTime = MAX_TIME
    for i in range(MAX_TIME):
        if bessieCan[i] and elsieCan[i]:
            earliestMeetingTime = i
            break

    if earliestMeetingTime == MAX_TIME:
        print("IMPOSSIBLE")
    else:
        print(earliestMeetingTime)

if __name__ == "__main__":
    main()