₦airaland Forum

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;
}
}

i can't explain, ni ojuelegba

Only some part I know I can explain but not all.

promise10:
Only some part I know I can explain but not all.

Please do explain the part u know.