PROBLEM LINK:
Practice
Contest
DIFFICULTY:
Simple
PREREQUISITES:
Graph theory, Shortest Paths
PROBLEM:
You’re given an N * N grid where (i,j)th entry is the distance between ith and jth point. You’re given M queries consisting of three points A, B, C. You’re task is to find out shortest distances : d(A, C) and d(A,B) + d(B, C).
QUICK EXPLANATION:
Pre-compute all pair-shortest paths using Floyd-Warshall algorithm. Solve every query in O(1) time.
DETAILED EXPLANATION:
Number of queries is so large that we can’t hope to find the shortest distance separately for each query. So we must do some precomputation so that we can answer individual queries fast enough. But as vertices change with each individual query, we can’t precompute distances from some points only, we need all pair shortest paths. Once we figure out this much, we could choose one of the algorithms for all pair shortest paths. The most common and simplest algorithm is Floyd Warshall which has a runnning time of O(N3)
Those of you who don’t know this algorithm, let me describe it a little here and you can follow up in detail in any algorithms book. Floyd Warshall is essentially a DP algorithm. DP state is d(i, j, k) which denotes the shortest distance between vertices j and k such that only vertices 1…i are allowed to be intermediate vertices. Base case is when i = 0 and it means shortest paths between vertices when no intermediate vertices are allowed. This is same as edge lengths between pair of vertices. After that when we include a new ith vertex, shortest path between j and k might not change in which case it’d be d(i-1, j, k) or it might change. It’d change iff ith vertex appears on the shortest path in which case its value would be d(i-1, j, i) + d(i-1, i, k).
We can save space by storing the dp for different values of i in the same 2D array. Sample code follows:
for i from 1 to N
for j from 1 to N
dist[j][k] = adj[j][k] // adj[j][k] is the adjacency matrix, as given in the problem
for i from 1 to N
for j from 1 to N
for k from 1 to N
dist[j][k] = min(dist[j][k], dist[j[i] + dist[i][k])
SETTER’S SOLUTION:
Can be found here.
TESTER’S SOLUTION:
Can be found here.
5 Likes
Did Anyone try dijkstra’s algo for this problem???I am getting WA and I am unable to find any test case for which I get the incorrect output…
I implemented floyd warshall in python for this problem but it gives TLE T_T
how come? aren’t the time-limit suppose to be fair for all languages?
Also isn’t it weird how there are no accepted python solutions for HOMEDEL?
Same problem. Implemented Floyd Warshall algorithm in python. Got TLE
Tried the same in java and it got accepted. To anyone who’s reading this “DON’T IMPLEMENT THIS ONE IN PYTHON”. You’ll get TLE. If you do implement this one in PYTHON then please speak about it in this discussion.
Yes, i solved it using Dijkstra’s algorithm. Here is the link:
http://www.codechef.com/viewsolution/1216567
TLE (Time Limit Exceeded) in Java: Not a problem with algorithm, but how reading input was expected!
After submitting several solutions with algorithm variants, I submitted one doing basically nothing and it also failed with TLE.
I saw accepted Java solutions (Thank you @ ksmehs
CodeChef: Practical coding for everyone), changed only scanner from buffered input … and it worked!!
My solution with some extra debug lines:
public class FloydTraveler
{
final static boolean DEBUG=false;
public static int MAX_WEIGHT=100000;
int nNodes;
int weight[][];
int bestDistance[][];
int bestNextNode[][];
public FloydTraveler(int nNodes){
this.nNodes=nNodes;
weight=new int[nNodes][nNodes];
bestDistance=new int[nNodes][nNodes];
if (DEBUG) bestNextNode=new int[nNodes][nNodes];
}
public void fillRandomWeights() {
int iFrom,iTo;
Random random= new Random();
for(iFrom=0; iFrom<nNodes;iFrom++) {
for(iTo=0; iTo<nNodes;iTo++) {
bestDistance[iFrom][iTo]= weight[iFrom][iTo] = iFrom==iTo?0:random.nextInt(MAX_WEIGHT);
if (DEBUG) bestNextNode[iFrom][iTo] = iTo;
}
}
}
public void readWeights(Scanner in) {
for(int iFrom=0; iFrom<nNodes;iFrom++) {
for(int iTo=0; iTo<nNodes;iTo++) {
bestDistance[iFrom][iTo]= weight[iFrom][iTo]= in.nextInt();
if (DEBUG) bestNextNode[iFrom][iTo] = iTo;
}
}
}
public void optimizeDistances(){
int iFrom, iTo, iMid;
int newDistance;
for (iMid=0;iMid<nNodes;iMid++) {
for (iFrom=0; iFrom<nNodes;iFrom++)
if (iFrom!=iMid) {
for (iTo=0; iTo<nNodes; iTo++)
if (iTo!=iFrom && iTo!=iMid) {
newDistance= bestDistance[iFrom][iMid]+bestDistance[iMid][iTo];
if (newDistance<bestDistance[iFrom][iTo]) {
if (DEBUG) System.out.println("\t["+iFrom+"->"+iTo+"] improved from "+bestDistance[iFrom][iTo]+" to "+newDistance + " through ["+iMid+"]");
bestDistance[iFrom][iTo]=newDistance;
if (DEBUG) bestNextNode[iFrom][iTo]=iMid;
}
}
}
}
}
public int getDistance(int iFrom, int iTo) {
if (DEBUG) System.out.println("\t"+getRoute(iFrom,iTo));
return bestDistance[iFrom][iTo];
}
public String getRoute(int iFrom, int iTo) {
StringBuffer route= new StringBuffer();
while(iFrom!=iTo) {
route.append(Integer.toString(iFrom));
route.append("->");
iFrom= bestNextNode[iFrom][iTo];
}
route.append(Integer.toString(iTo));
return route.toString();
}
public static void main(String[] args) {
long startInstant=0,finishInstant=0, totalExecTime=0;
Scanner in = new Scanner(System.in);
int nStreets= in.nextInt();
FloydTraveler proc= new FloydTraveler(nStreets);
if (DEBUG&&nStreets>10)
proc.fillRandomWeights();
else
proc.readWeights(in);
if (DEBUG) startInstant = System.nanoTime();
proc.optimizeDistances();
if (DEBUG) {
finishInstant = System.nanoTime();
totalExecTime += (finishInstant - startInstant);
System.out.printf("Distance optimization: %,10d ns\n", totalExecTime);
}
int scenarios= in.nextInt();
for (int sc=0; sc<scenarios && in.hasNextInt(); sc++) {
int startSt= in.nextInt();
int gasSt = in.nextInt();
int destSt= in.nextInt();
if (DEBUG) startInstant = System.nanoTime();
int directTime= proc.getDistance (startSt,destSt);
int actualTime= proc.getDistance(startSt,gasSt)+proc.getDistance(gasSt,destSt);
if (DEBUG) {
finishInstant = System.nanoTime();
totalExecTime += (finishInstant - startInstant);
System.out.printf("%d) actualTime=%3d. save=%3d. execution Time %,10d ns\n", sc + 1, actualTime, actualTime - directTime, finishInstant - startInstant);
} else
System.out.println(actualTime+" "+(actualTime-directTime));
}
if (DEBUG) System.out.printf("Total execution Time %,10d ns\n",totalExecTime);
in.close();
}
}