java - UVA#523 最低运输成本

Question

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

我不知道自己现在在做什么。我不知道为什么我会产生错误的值。在寻找最短路径后，我打印出了数组。它会产生这样的结果:

[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]

示例输入是:

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

使用示例输入，我生成输出:

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

如果我查看我的数组，它似乎是正确的。但正确答案是:

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

<小时/>

我想我错过了添加税款，但我不知道在哪里添加。我尝试在执行最短路径时将 tax[j] 添加到 path[i][j]，然后减去 tax[x-1] 和 tax[y-1] (x-1 是我的来源，y-1 是我的目的地)。它不起作用，并且弄乱了我的路径数组(它为循环提供了值；我真的不需要它)。我真的不知道该把税放在哪里。

这是我的引用代码:

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

适用税款:

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

如果你有一条路径，那么你:

a -> b -> c -> d

然后您应该包括路径的成本 (a,b) + 税(b) + (b,c) + 税(c) + (c,d)。

为了将其实现到您的算法中，您应该能够将城市税添加到路径长度中，如下所示:

如果您知道从 a 开始并在 d 结束，则任何到城市 x 的有向路径(其中 x 不是 a 或 b)都应被视为 x 的成本 + 城市 x 的税费。

您需要将路径成本值恢复为要计算其值(value)的下一条路径的原始值，并为新的起点和目的地重新添加税值。