// Create a modified graph in which each junction is represented by // several nodes, one for each direction of entry from a neighbor. // // Add connections based on turning constraints. // // Step 1: Add a start node s connected to each nbr of junction 1; weights = 0. // Step 2: Find shortest paths from s. // Step 3: Modify s so that now s points to all nodes for junction // d, edges labeled with distances found in Step 1 // Step 4: Find shortest paths from s. Answer is min of all the "d" nodes // in the new graph. import java.util.Scanner; import java.util.Arrays; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Comparator; public class Biotrip_BobR { public static Scanner in; public static int n,d,a1,a2; // inputs public static int n2; // # nodes in modified graph public static Integer onbr[][]; // neighbor list for input graph public static Integer odist[][]; // edge distances for input graph public static int node[][]; // node[i][j] = new graph node # for // junction i ENTERED FROM j public static int ang[][]; // exit angle from i to j (entry angle from j to i) public static Integer newnbr[][]; // neighbor list for modified graph public static Integer newd[][]; // edge distances for modified graph public static int dijdist[]; // dijkstra distance from start node public static int dijprev[]; // dijkstra previous node on shortest path public static PriorityQueue pq; public static void main(String[] args) { in = new Scanner(System.in); n = in.nextInt(); d = in.nextInt(); a1 = in.nextInt(); a2 = in.nextInt(); // original input graph (0-adjusted numbering): onbr = new Integer[n][0]; odist = new Integer[n][0]; node = new int[n][n]; ang = new int[n][n]; n2 = 0; for (int i = 0; i < n; i++) Arrays.fill(node[i],-1); for (int i = 0; i < n; i++) { int m = in.nextInt(); ArrayList nb = new ArrayList(); // temp nbr list ArrayList ds = new ArrayList(); // temp dist list for (int j = 0; j < m; j++) { int dj = in.nextInt()-1; // destination of this road int lj = in.nextInt(); // length of this road int aj = in.nextInt(); // exit angle of this road // input graph: nb.add(dj); ds.add(lj); // modified graph: node[i][dj] = n2++; ang[i][dj] = aj; } onbr[i] = nb.toArray(onbr[i]); odist[i] = ds.toArray(odist[i]); } // Now build up the new graph using the old one and the angle info: // We've already created the blank nodes; now we fill in edges. // There is an edge between node[i][j] and node[k][i] if ang[i][k] // lies between x-a2 and x+a1, where x = ang[i][j]+180. dijdist = new int[n2+1]; Arrays.fill(dijdist,Integer.MAX_VALUE/2); dijdist[n2] = 0; dijprev = new int[n2+1]; Arrays.fill(dijprev,-1); newnbr = new Integer[n2+1][0]; newd = new Integer[n2+1][0]; for (int i = 0; i < n; i++) { for (int p = 0; p < onbr[i].length; p++) { int j = onbr[i][p]; int nd = node[i][j]; int x = mod(ang[i][j]+180,360); // direction of travel from j to i ArrayList nb = new ArrayList(); ArrayList ds = new ArrayList(); for (int q = 0; q < onbr[i].length; q++) { int k = onbr[i][q]; int y = ang[i][k]; if (y < x) y += 360; int diff = y-x; if ((diff <= 180 && diff <= a1) || diff >= 180 && (360-diff) <= a2) { nb.add(node[k][i]); ds.add(odist[i][q]); } newnbr[nd] = nb.toArray(newnbr[nd]); newd[nd] = ds.toArray(newd[nd]); } } } // Add a start node (numbered n2) going to all the neighbors of // the "0" nodes: ArrayList nbr = new ArrayList(); ArrayList dis = new ArrayList(); for (int i = 0; i < onbr[0].length; i++) { nbr.add(node[onbr[0][i]][0]); dis.add(odist[0][i]); } newnbr[n2] = nbr.toArray(newnbr[n2]); newd[n2] = dis.toArray(newd[n2]); // Now run Dijkstra's algorithm with graph newnbr, newd and // initial values dijdist, dijprev. pq = new PriorityQueue(new Comparator() { public int compare(Integer a, Integer b) { return dijdist[a] - dijdist[b]; } }); for (int i = 0; i < n2+1; i++) pq.add(i); dijkstra(); // Now work back to node 0: node n2 now points to the destination nodes. newnbr[n2] = new Integer[0]; newd[n2] = new Integer[0]; nbr = new ArrayList(); dis = new ArrayList(); for (int i = 0; i < onbr[d-1].length; i++) { nbr.add(node[d-1][onbr[d-1][i]]); dis.add(dijdist[node[d-1][onbr[d-1][i]]]); } newnbr[n2] = nbr.toArray(newnbr[n2]); newd[n2] = dis.toArray(newd[n2]); Arrays.fill(dijdist,Integer.MAX_VALUE/2); dijdist[n2] = 0; Arrays.fill(dijprev,-1); if (!pq.isEmpty()) { System.out.println("Error"); pq.clear(); } for (int i = 0; i < n2+1; i++) pq.add(i); dijkstra(); int min = Integer.MAX_VALUE; int mind = -1; for(int i = 0; i < onbr[0].length; i++) { Integer j = onbr[0][i]; int nd = node[0][j]; if (dijdist[nd] < min) { min = dijdist[nd]; mind = nd; } } if (min < Integer.MAX_VALUE/2) System.out.println(min); else System.out.println ("impossible"); /* System.out.print("PATH back: "+mind); while (dijprev[mind] >= 0) { mind = dijprev[mind]; System.out.print(" "+mind); } System.out.println(); */ } // computes p mod q, correct for negative p public static int mod(int p, int q) { if (p >= 0) return p % q; else return (q + p % q)%q; } public static void displayorig(Integer[][] onbr,Integer[][] odist) { for (int i = 0; i < onbr.length; i++) { System.out.print(i+": "); for (int j = 0; j < onbr[i].length; j++) { System.out.print(onbr[i][j] +" ("+odist[i][j]+") "); } System.out.println(); } } public static void dijkstra() { while (!pq.isEmpty()) { Integer i = pq.poll(); for (int p = 0; p < newnbr[i].length; p++) { Integer j = newnbr[i][p]; if (!pq.contains(j)) continue; if (dijdist[i]+newd[i][p] < dijdist[j]) { pq.remove(j); dijdist[j] = dijdist[i]+newd[i][p]; dijprev[j] = i; pq.add(j); } } } } }