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]);
      }
    }
  }

}

以上就是關于【USACO 2015 January Contest, Bronze Problem 4. Meeting Time】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學申請的“核武器”來了！

2026理工科競賽“大洗牌”：線上考試終結、報名門檻收緊、晉級規則重塑...你準備好了嗎？