NewStats: 3,261,342 , 8,173,727 topics. Date: Wednesday, 28 May 2025 at 09:28 PM 3l2z1q

6z3e3g

Tosinosu2011's Posts 6v5c6k

Tosinosu2011's Posts

(2) (3) (of 3 pages)

Tosinosu2011: 1:20am On Nov 30, 2016
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.
Tosinosu2011: 2:51pm On Oct 25, 2016
add 07063491221
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"wink;

// 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"wink;
for (edge x: roads)
if (x.toll > 0)
sb.append(x.ID+" "+ x.toll+"\n"wink;
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>winkg[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>winkg[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;
}
}
Tosinosu2011: 10:31am 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"wink;

// 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"wink;
for (edge x: roads)
if (x.toll > 0)
sb.append(x.ID+" "+ x.toll+"\n"wink;
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>winkg[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>winkg[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;
}
}




Please Mr Fulaman Can you explain the Code above to me. It was an assignment in school that i did not understand.
Tosinosu2011: 11:03am On Jun 16, 2016
Please i want explanation and solution for the problem in the attachment. Thanks in advance.

Tosinosu2011: 7:32am On Mar 02, 2016
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
Tosinosu2011: 6:10pm On Dec 25, 2015
OP please which scholarship did you applied for that earned you this testimony
Tosinosu2011: 6:14pm On Dec 16, 2015
capofwesh:

Am in a similar situation... Wat did dey tell u guys
. They said it would get to us?
Tosinosu2011: 1:18pm On Dec 16, 2015
But i don't know why they did not issue certificate for those who held theirs in Lagos o.

1 Like

Tosinosu2011: 9:23pm On Nov 28, 2015
pls i nid it too [email protected]
Tosinosu2011: 7:41pm On Nov 22, 2015
Is dere anybody from polytechnic who wrote the exam?
Tosinosu2011: 10:39am On Oct 29, 2015
Tosinosu2011: 10:37am On Oct 29, 2015
pls i need the past question at [email protected].
Tosinosu2011: 4:26pm On Oct 21, 2015
i wrote d aptitude test bt am yet to recieve any email.
Tosinosu2011: 10:30pm On Jul 16, 2012
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.