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]してから、 and (はソース、目的地) を減算してみました。それは機能せず、パス配列を台無しにします (ループに値を与えます。実際には必要ありません)。どこに税金を入れたらいいのかわからない。path[i][j]tax[x-1]tax[y-1]x-1y-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;
}
}