USACO 2015 January Contest, Bronze Problem 4. Meeting Time

原题下载

USACO2015JAN-B4

答案

(Analysis by Nick Wu)

For each of Bessie and Elsie, we will simply try all possible paths that they can take to get from field 1 to field N. Because there are only at most 14 fields in between field 1 and field N, and all paths go downward, there are only 2^{14} = 16384 different paths that each of Bessie and Elsie could take. We can recursively keep track of which field Bessie and Elsie are at, along with how far they've walked, and keep track of whether it's possible for them to get to field N in K units of time.

After we've figured out this information, noting that the longest path can be at most 15000 units of time, we can simply loop to see if both Bessie and Elsie can make it to field N in K units of time, and report the smallest such time.

Here is my Java solution:

import java.io.*;
import java.util.*;
public class meeting {
  static int[][] bessieGrid;
  static int[][] elsieGrid;

  static boolean[] bessieCan;
  static boolean[] elsieCan;

  static int n;
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());
    bessieGrid = new int[n][n];
    elsieGrid = new int[n][n];
    for(int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int x = Integer.parseInt(st.nextToken())-1;
      int y = Integer.parseInt(st.nextToken())-1;
      bessieGrid[x][y] = Integer.parseInt(st.nextToken());
      elsieGrid[x][y] = Integer.parseInt(st.nextToken());
    }
    bessieCan = new boolean[20000];
    elsieCan = new boolean[20000];
    dfs(bessieGrid, bessieCan, 0, 0);
    dfs(elsieGrid, elsieCan, 0, 0);
    int best = Integer.MAX_VALUE;
    for(int i = 0; i < bessieCan.length; i++) {
      if(bessieCan[i] && elsieCan[i]) {
        best = i;
        break;
      }
    }
    if(best == Integer.MAX_VALUE) {
      pw.println("IMPOSSIBLE");
    }
    else {
      pw.println(best);
    }
    pw.close();
  }

  public static void dfs(int[][] dist, boolean[] can, int currV, int currD) {
    if(currV == n-1) {
      can[currD] = true;
      return;
    }
    for(int a = currV+1; a < n; a++) {
      if(dist[currV][a] > 0) {
        dfs(dist, can, a, currD + dist[currV][a]);
      }
    }
  }

}