Hugo Thi Chay
unknown
java
a year ago
1.5 kB
11
Indexable
package backtrack; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class HugoThiChay { static int energy; static int distance; static int[][] runType; static int minTime; public static void main(String[] args) throws FileNotFoundException { System.setIn(new FileInputStream("input.txt")); Scanner sc = new Scanner(System.in); int test_case = sc.nextInt(); for (int tc = 1; tc <= test_case; tc++) { energy = sc.nextInt(); distance = sc.nextInt(); runType = new int[5][2]; for (int i = 0; i < 5; i++) { int m = sc.nextInt(); int s = sc.nextInt(); int e = sc.nextInt(); runType[i][0] = m * 60 + s; runType[i][1] = e; } minTime = 16800; backtrack(0,0, energy, 0); System.out.println("Case #" + tc); if (minTime == 16800) { System.out.println(-1); } else System.out.println(minTime / 60 + " " + minTime % 60); } } public static void backtrack(int localDistance,int index, int remainEnergy, int time) { if (time >= minTime) return; if(remainEnergy < 0 || index == 5) return; if (localDistance == distance) { minTime = Math.min(minTime, time); return; } for(int i = 0;i<2;i++){ if(i == 0){ backtrack(localDistance, index + 1, remainEnergy, time); } else{ backtrack(localDistance + 1,index, remainEnergy - runType[index][1], time + runType[index][0]); } } } }
Editor is loading...
Leave a Comment