Programming Contest: Next Door
Description
This problem analyzes information about a network, including details of which routers are connected to each other and which computers are connected to which routers. The program is to explain the path between two computers that the data must travel. The most efficient path should be displayed. Note that this program was a bit of a pain to code, but the heart of it is simply Floyd-Warshall’s algorithm.
[ complete description ] [ nextdoor.java ]
Sample Input
2 3 4 2 Router1 Router2 Router2 Router3 Router3 Router4 Comp1 Router1 Comp2 Router2 Comp3 Router3 Comp4 Router4 Comp1 Comp2 Comp1 Comp3 1 3 3 Router1 Router2 Comp1 Router1 Comp2 Router1 Comp3 Router2 Comp1 Comp2 Comp2 Comp3 Comp1 Comp3
Sample Output
Data set #1: Comp1 to Comp2 requires 2 hops: Router1 Router2 Comp1 to Comp3 requires 3 hops: Router1 Router2 Router3 Data set #2: Comp1 to Comp2 requires 1 hops: Router1 Comp2 to Comp3 requires 2 hops: Router1 Router2 Comp1 to Comp3 requires 2 hops: Router1 Router2
Solution
String ans;
int[][] path;
int[][] grid;
ArrayList<String> routers;
ArrayList<String> rconnections;
ArrayList<String> computers;
ArrayList<String> comprouter;
int INF = 500;
public void go() throws Exception
{
Scanner in = new Scanner(new File("nextdoor.in"));
int cases = in.nextInt();
for(int x=0; x<cases; x++)
{
int r = in.nextInt(), c = in.nextInt(), t = in.nextInt();
in.nextLine();
String cur;
String curarray[];
routers = new ArrayList<String>();
rconnections = new ArrayList<String>();
computers = new ArrayList<String>();
comprouter = new ArrayList<String>();
// read routers
for(int y=0; y<r; y++)
{
cur = in.nextLine();
rconnections.add(cur);
curarray = cur.split(" ");
if(!routers.contains(curarray[0]))
routers.add(curarray[0]);
if(!routers.contains(curarray[1]))
routers.add(curarray[1]);
}
grid = new int[routers.size()][routers.size()];
path = new int[routers.size()][routers.size()];
for(int y=0; y<routers.size(); y++)
for(int z=0; z<routers.size(); z++)
{
grid[y][z] = (y==z)? 0 : INF;
path[y][z] = (y==z||path[y][z]==INF)? -1 : y;
}
for(int y=0; y<rconnections.size(); y++)
{
curarray = rconnections.get(y).split(" ");
grid[routers.indexOf(curarray[0])][routers.indexOf(curarray[1])] = 1;
grid[routers.indexOf(curarray[1])][routers.indexOf(curarray[0])] = 1;
}
// Floyd-Warshall's
for(int k=0; k<routers.size(); k++)
for(int i=0; i<routers.size(); i++)
for(int j=0; j<routers.size(); j++)
{
if(grid[i][j]>grid[i][k]+grid[k][j])
{
grid[i][j]=grid[i][k]+grid[k][j];
path[i][j]=path[k][j];
}
}
// read computers
for(int y=0; y<c; y++)
{
cur = in.nextLine();
curarray = cur.split(" ");
computers.add(curarray[0]);
comprouter.add(curarray[1]);
}
// do test cases
prnln("Data set #"+(x+1)+":");
for(int y=0; y<t; y++)
{
cur = in.nextLine();
curarray = cur.split(" ");
ans = comprouter.get(computers.indexOf(curarray[0]));
int count = 1 + printpath(routers.indexOf(comprouter.get(computers.indexOf(curarray[0]))),
routers.indexOf(comprouter.get(computers.indexOf(curarray[1]))));
prnln(""+curarray[0]+" to "+curarray[1]+" requires "+count+" hops: "+ans);
}
prnln("");
}
}
public int printpath(int from, int to)
{
int count = 0;
if(path[from][to]!=from && from!=to)
count = printpath(from, path[from][to]) + printsubpath(path[from][to], to);
else if(from!=to)
{
ans += " "+routers.get(to);
count++;
}
return count;
}
public int printsubpath(int from, int to)
{
int count = 0;
if(path[from][to]!=from && from!=to)
count = printpath(from, path[from][to]) + printpath(path[from][to], to);
if(from!=to)
{
ans += " "+routers.get(to);
count++;
}
return count;
}