UVA#523 Minimum Transport Cost

Question

UVA link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=464

I'm lost as to what I'm doing now. I don't know why I'm producing incorrect values. I printed out the array after I looked for shortest path. And it produces this:

[0, 3, 8, 8, 4]
[3, 0, 5, 11, 7]
[8, 5, 0, 9, 12]
[8, 11, 9, 0, 4]
[4, 7, 12, 4, 0]

The sample input is:

1

0 3 22 -1 4
3 0 5 -1 -1
22 5 0 9 20
-1 -1 9 0 4
4 -1 20 4 0
5 17 8 3 1
1 3
3 5
2 4

With the sample input, I produce the output:

From 1 to 3 :
Path: 1-->2-->3

Total cost :8
From 3 to 5 :
Path: 3-->2-->5
Total cost :12

From 2 to 4 :
Path: 2-->5-->4
Total cost :11

If I look at my array, it seems to be correct. But the correct answer is:

From 1 to 3 :
Path: 1-->5-->4-->3
Total cost : 21

From 3 to 5 :
Path: 3-->4-->5
Total cost : 16

From 2 to 4 :
Path: 2-->1-->5-->4
Total cost : 17

---

I think I missed adding the tax, but I don't know where to add it. I tried adding tax[j] to the path[i][j] while doing the shortest path, and then subtracting the tax[x-1] and tax[y-1] (x-1 is my source, y-1 is my destination). It doesn't work, and messes up my path array (it gives value to loops; I don't really need that). I really don't know where to put the tax.

Here is my code for reference:

import java.util.*;
public class Main{
public static final int INF = 9999999;
public static int[][] path;
public static int[][] next;
public static int[] tax;
public static void main(String[] adsf){
    Scanner pp = new Scanner(System.in);
    int testCases = pp.nextInt();
    boolean first = true;
    pp.nextLine();
    pp.nextLine();
    while(testCases-- >0){
        String[] s1 = pp.nextLine().split(" ");
        int size = s1.length;
        path = new int[size][size];
        next = new int[size][size];
        for(int i = 0; i < path.length; i++)
            Arrays.fill(path[i],INF);
        tax = new int[size];
        for(int j = 0; j < path[0].length; j++){
            path[0][j] = Integer.parseInt(s1[j]);
            if(path[0][j]==-1)
                path[0][j]=INF;
        }
        for(int i = 1; i < path.length;i++){
            s1 = pp.nextLine().split(" ");
            for(int j = 0; j < path[0].length; j++){
                path[i][j] = Integer.parseInt(s1[j]);
                if(path[i][j]==-1)
                    path[i][j]=INF;
            }
        }
        for(int k=0; k<tax.length;k++){
            tax[k] = pp.nextInt();
        } pp.nextLine();    
        apsp();
        int x,y;
        //for(int i = 0; i < size; i++)
        //System.out.println(Arrays.toString(path[i]));
        while(pp.hasNextInt()){
            if(!first)
            System.out.println();
            x=pp.nextInt();
            y=pp.nextInt();
            int cost = path[x-1][y-1];
            System.out.println("From "+x+" to "+y+" :");
            System.out.print("Path: ");
            ArrayList<Integer> print = getpath(x-1,y-1);
            for(int l = 0; l < print.size(); l++){
                System.out.print(print.get(l)+1);
                if(l!=print.size()-1) System.out.print("-->");
                else System.out.println();
            }
            System.out.println("Total cost :"+cost);
            first = false;
        }
    }
}
public static void apsp(){
    for(int k=0;k<path.length;k++){
        for(int i=0;i<path.length;i++){
            for(int j=0;j<path.length;j++){
                if (path[i][k] + path[k][j] + tax[j] < path[i][j] + tax[j]) {
                    path[i][j] = path[i][k]+path[k][j];
                    next[i][j] = k;
                } else{
                    path[i][j] = path[i][j];
                }
            }   
        }   
    }
}
public static ArrayList<Integer> getpath (int i, int j) {
    ArrayList<Integer> pat = getMidPath(i,j);
    pat.add(0,i);
    pat.add(j);
    return pat;
}
public static ArrayList<Integer> getMidPath(int i, int j){
    if(next[i][j]==0)
        return new ArrayList<Integer>();
    ArrayList<Integer> pat = new ArrayList<Integer>();
    pat.addAll(getMidPath(i,next[i][j]));
    pat.add(next[i][j]);
    pat.addAll(getMidPath(next[i][j],j));
    return pat;
}
}

Answer 1

The tax is applied:

whenever any cargo passing through one city, except for the source and the destination cities.

So you if you have a path:

a -> b -> c -> d

Then you should include the cost of the path (a,b) + tax(b) + (b,c) + tax(c) + (c,d).

For implementing that into your algorithm, you should be able to add the city taxes to the path lengths like this:

If you know you're starting at a and ending at d, then any directed path to a city x, where x isn't a or b, should be treated as the cost of x + the tax at city x.

You will need to revert the path cost values back to the original ones for the next path you want to calculate the value of and re-add the tax values in for the new starting point and destination.