Welcome, Guest: Register On Nairaland / LOGIN! / Trending / Recent / NewStats: 3,194,291 members, 7,954,153 topics. Date: Friday, 20 September 2024 at 01:18 PM |
Nairaland Forum / Science/Technology / Programming / Explain This Code And Get Commended (1608 Views)
Can Someone Help Me Explain This Code Line? / Java Programmers ,I Need Help Fixing This Code. / Please Someone Should Help Me With This Code. (2) (3) (4)
Explain This Code And Get Commended by Tosinosu2011: 10:46am On Jun 17, 2016 |
package FareAndBalanced; //Solution to 2009 World Finals Problem E: Fare and Balanced import java.util.*; import java.io.*; public class fare { final public static int NOPATH = 1000000000; public static int[] minDist; public static int[] maxDist; public static int n; public static edge[] roads; public static int[] minDFromEnd; public static int[] maxDFromEnd; public static ArrayList[] graph; public static ArrayList[] revGraph; public static void main(String[] args) throws Exception { BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tok = new StringTokenizer(stdin.readLine()); n = Integer.parseInt(tok.nextToken()); int e = Integer.parseInt(tok.nextToken()); int loop = 1; // Process each case. while (n != 0) { roads = new edge[e]; // Read in graph. graph = new ArrayList[n]; for (int i=0; i<n; i++) graph[i] = new ArrayList<edge>(); // We also need edges stored in "reverse" order. revGraph = new ArrayList[n]; for (int i=0; i<n; i++) revGraph[i] = new ArrayList<edge>(); for (int i=0; i<e; i++) { tok = new StringTokenizer(stdin.readLine()); int v1 = Integer.parseInt(tok.nextToken()) - 1; int v2 = Integer.parseInt(tok.nextToken()) - 1; int c = Integer.parseInt(tok.nextToken()); roads[i] = new edge(v1, v2, c, i+1); graph[roads[i].v1].add(roads[i]); revGraph[roads[i].v2].add(roads[i]); } minDist = new int[n]; maxDist = new int[n]; minDFromEnd = new int[n]; maxDFromEnd = new int[n]; boolean res = solve(); // Can't do it. if (!res) System.out.println("Case "+loop+": No solution" // Usual case. else { // Calculate number of roads to toll. int numToll = 0; for (edge x: roads) if (x.toll > 0) numToll++; // Output each road with a toll. StringBuffer sb = new StringBuffer(); sb.append("Case "+loop+": "+numToll+" "+maxDist[n-1]+"\n" for (edge x: roads) if (x.toll > 0) sb.append(x.ID+" "+ x.toll+"\n" System.out.print(sb); } // Get next case. loop++; tok = new StringTokenizer(stdin.readLine()); n = Integer.parseInt(tok.nextToken()); e = Integer.parseInt(tok.nextToken()); } } public static boolean solve() throws Exception { // Pre-compute shortest and longest distances, from both residential area and downtown. solveMinD(minDist, true); solveMaxD(maxDist, true); solveMinD(minDFromEnd, false); solveMaxD(maxDFromEnd, false); // Go through each road. for (int i=0; i<roads.length; i++) { int a = roads[i].v1; int b = roads[i].v2; if (minDist[a] == maxDist[a] && minDist[b] != maxDist[b] && maxDist[n-1] - maxDist[a] != roads[i].c + maxDFromEnd[b]) roads[i].toll = maxDist[n-1] - maxDist[a] - (roads[i].c + maxDFromEnd[b]); // Means it's impossible since we could have a toll before and one after. if (minDist[a] != maxDist[a] && minDFromEnd[a] != maxDFromEnd[a]) return false; } // We made it! return true; } // Solves for all min distances. If flag = true, source = residential, otherwise source = downtown. public static void solveMinD(int[] myMinDist, boolean flag) { Arrays.fill(myMinDist, NOPATH); int source = flag ? 0 : n-1; int dest = flag ? n-1 : 0; myMinDist[source] = 0; recMinD(myMinDist, dest, flag); } // Recursively finds the shortest distance from source to v. If flag = true, source = residential, otherwise downtown. public static int recMinD(int[] myMinDist, int v, boolean flag) { // We solved it already. if (myMinDist[v] != NOPATH) return myMinDist[v]; // Tells us which graph to use. ArrayList[] g = flag ? revGraph : graph; int res = NOPATH; // Try all edges leaving v in the direction we seek. for (int i=0; i<g[v].size(); i++) { edge e = ((ArrayList<edge>g[v]).get(i); int tmp = flag ? e.c + recMinD(myMinDist, e.v1, flag) : e.c + recMinD(myMinDist, e.v2, flag); res = Math.min(res, tmp); } // Store result and return. myMinDist[v] = res; return res; } // Solves for all max distances. If flag = true, source = residential, otherwise source = downtown. public static void solveMaxD(int[] myMaxDist, boolean flag) { Arrays.fill(myMaxDist, -1); int source = flag ? 0 : n-1; int dest = flag ? n-1 : 0; myMaxDist[source] = 0; recMaxD(myMaxDist, dest, flag); } // Recursively finds the longest distance from source to v. If flag = true, source = residential, otherwise downtown. public static int recMaxD(int[] myMaxDist, int v, boolean flag) { // We did this already. if (myMaxDist[v] != -1) return myMaxDist[v]; // Tells us which graph to use. ArrayList[] g = flag ? revGraph : graph; int res = 0; // Try all edges from v in direction we want. for (int i=0; i<g[v].size(); i++) { edge e = ((ArrayList<edge>g[v]).get(i); int tmp = flag ? e.c + recMaxD(myMaxDist, e.v1, flag) : e.c + recMaxD(myMaxDist, e.v2, flag); res = Math.max(res, tmp); } // Store answer and return. myMaxDist[v] = res; return res; } } class edge { public int v1; public int v2; public int c; public int ID; public int toll; public edge(int myv1, int myv2, int myc, int myID) { v1 = myv1; v2 = myv2; c = myc; ID = myID; toll = 0; } } |
Re: Explain This Code And Get Commended by adexlamex(m): 10:50am On Jun 17, 2016 |
i can't explain, ni ojuelegba 1 Like |
Re: Explain This Code And Get Commended by promise10: 3:23pm On Jun 17, 2016 |
Only some part I know I can explain but not all. |
Re: Explain This Code And Get Commended by 4kings: 11:12pm On Jul 30, 2016 |
promise10:Please do explain the part u know. |
(1) (Reply)
How Do U Program? Debug As U Code Or Debug After Coding? Which Is Best? / Pls I Need A Book On System Programing / HELP: Programmers In The House Please Help Out
(Go Up)
Sections: politics (1) business autos (1) jobs (1) career education (1) romance computers phones travel sports fashion health religion celebs tv-movies music-radio literature webmasters programming techmarket Links: (1) (2) (3) (4) (5) (6) (7) (8) (9) (10) Nairaland - Copyright © 2005 - 2024 Oluwaseun Osewa. All rights reserved. See How To Advertise. 23 |