NewStats: 3,261,342 , 8,173,727 topics. Date: Wednesday, 28 May 2025 at 09:28 PM 3l2z1q6z3e3g |
(2) (3) (of 3 pages)
![]() |
Am a student of a federal university in Nigeria. Please help me with my school fees which will end this coming Friday. The amount is 48k. Any amount you help me with will be highly appreciated. number is 2080313234 UBA bank. thanks in anticipation.
|
![]() |
add 07063491221
|
![]() |
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> ![]() 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> ![]() 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; } } |
![]() |
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> ![]() 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> ![]() 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; } } Please Mr Fulaman Can you explain the Code above to me. It was an assignment in school that i did not understand. |
![]() |
Please i want explanation and solution for the problem in the attachment. Thanks in advance.
|
![]() |
please i need a program that allow s to enter d number of tyres and it would be evenly divided through bicycle, car, and trycycle tyres. eg 9 tires will be: 1car, 1trycycle and 1bicycle. the program sud be in java. tenks
|
![]() |
OP please which scholarship did you applied for that earned you this testimony
|
![]() |
capofwesh:. They said it would get to us? |
![]() |
But i don't know why they did not issue certificate for those who held theirs in Lagos o.
1 Like |
![]() |
pls i nid it too [email protected]
|
![]() |
Is dere anybody from polytechnic who wrote the exam?
|
![]() |
![]() |
pls i need the past question at [email protected].
|
![]() |
i wrote d aptitude test bt am yet to recieve any email.
|
![]() |
true love is when ur guy dey play video game or dey watch football march and he pick ur call
1 Like |
(2) (3) (of 3 pages)
(Go Up)
Sections: How To . 38 Disclaimer: Every Nairaland member is solely responsible for anything that he/she posts or s on Nairaland. |