AllPairShortestPath.java

importjava.util.*;
importjava.lang.*;
importjava.io.*;
importjava.math.*;
importutils.io.FastReader;
/*
 * Author : joney_000[developer.jaswant@gmail.com]
 * Algorithm : All Pair Shortest Path
 * Platform : Codeforces
 * Ref : Time Complexity: O(N^3), Space Complexity: O(N^2)
 */

classA{ 

privateInputStreaminputStream ;
privateOutputStreamoutputStream ;
privateFastReaderin ;
privatePrintWriterout ;

privatefinalintBUFFER = 100005;

privatefinallongmod = 1000000000+7;
privatefinalintINF = Integer.MAX_VALUE;
privatefinallongINF_L = Long.MAX_VALUE / 10;

publicA(){}
publicA(booleanstdIO)throwsFileNotFoundException{
// stdIO = false;
if(stdIO){
inputStream = System.in;
outputStream = System.out;
 }else{
inputStream = newFileInputStream("input.txt");
outputStream = newFileOutputStream("output.txt");
 }
in = newFastReader(inputStream);
out = newPrintWriter(outputStream);
 }

finalintMAX_N = 100;
longcost[][] = newlong[MAX_N + 1][MAX_N + 1];
longweight[][] = newlong[MAX_N + 1][MAX_N + 1];

voidrun()throwsException{
intn = i();
intans = 0;
initialize();
out.write(""+ans+"\n");
 }

voidinitialize(){
for(inti = 1; i <= MAX_N; i++){
for(intj = 1; j <= MAX_N; j++){
weight[i][j] = INF_L;
if(i==j)weight[i][j] = 0L;
 }
 }
 }

voidallPairShortestPath(intn){
for (inti = 1; i <= n; i++){
for (intj = 1; j <= n; j++){
cost[i][j] = weight[i][j];
 }
 }
// order matters: k->i->j 
for(intk = 1; k <= n; k++){
for (inti = 1; i <= n; i++){
for (intj = 1; j <= n; j++){
if(cost[i][k] + cost[k][j] < cost[i][j]){
cost[i][j] = cost[i][k] + cost[k][j];
 }
 }
 }
 }
 }

inti()throwsException{
returnin.nextInt();
 }

longl()throwsException{
returnin.nextLong();
 }

doubled()throwsException{
returnin.nextDouble();
 }

charc()throwsException{
returnin.nextCharacter();
 }

Strings()throwsException{
returnin.nextLine();
 }

BigIntegerbi()throwsException{
returnin.nextBigInteger();
 }

privatevoidcloseResources(){
out.flush();
out.close();
return;
 }

// IMP: roundoff upto 2 digits 
// double roundOff = Math.round(a * 100.0) / 100.0;
// or
// System.out.printf("%.2f", val);

// print upto 2 digits after decimal
// val = ((long)(val * 100.0))/100.0; 

publicstaticvoidmain(String[] args) throwsjava.lang.Exception{

Adriver = newA(true);
driver.run();
driver.closeResources();
 }
}

classPairimplementsComparable<Pair>{
publicinta;
publicintb;

publicPair(){
this.a = 0;
this.b = 0;
 }

publicPair(inta,intb){
this.a = a;
this.b = b;
 }

publicintcompareTo(Pairp){
if(this.a == p.a){
returnthis.b - p.b; 
 }
returnthis.a - p.a; 
 }

@Override
publicStringtoString(){
return"a = " + this.a + " b = " + this.b;
 }
}