0

基本的に、行列の最短経路を見つけるためにフロイドのアルゴリズムを実装することを任されています。値 (私の場合は arg) が取り込まれ、行列はサイズ arg*arg になります。次の値の文字列は、受け取った順序でマトリックスに適用されます。最後に、-1 は無限大を表します。

正直に言うと、どこに問題があるのか​​わかりません。テストを実行すると、最初の 2 つは成功しますが、残りは失敗します。パスと一緒に最初の 2 つの失敗のみを投稿します。関連するコード セグメントのみを掲載します。

int arg, var, i, j;

cin >> arg;

int arr[arg][arg];

for (i = 0; i < arg; i++)
{
    for(j = 0; j < arg; j++)
    {
        cin >> var;
        arr[i][j] = var;
    }
}


for(int pivot = 0; pivot < arg; pivot++)
{
    for(i = 0; i < arg; i++)
    {
        for(j = 0; j < arg; j++)
        {
            if((arr[i][j] > (arr[i][pivot] + arr[pivot][j])) && ((arr[i][pivot] != -1) && arr[pivot][j] != -1))
            {
                arr[i][j] = (arr[i][pivot] + arr[pivot][j]);
                arr[j][i] = (arr[i][pivot] + arr[pivot][j]);
            }
        }
    }
}

そして、ここに私が受け取っている失敗があります。それらの残りの部分はどんどん長くなり、最大 20*20 の行列になるので、それは割愛します。

floyd> 
 * * * Program successfully started and correct prompt received. 

floyd 2 0 14 14 0
0 14 14 0 
floyd>   PASS  : Input "floyd 2 0 14 14 0" produced output "0 14 14 0".  

floyd 3 0 85 85 85 0 26 85 26 0
0 85 85 85 0 26 85 26 0 
floyd>   PASS  : Input "floyd 3 0 85 85 85 0 26 85 26 0" produced output "0 85 85 85 0 26 85 26 0".  

floyd 3 0 34 7 34 0 -1 7 -1 0
0 34 7 34 0 -1 7 -1 0 
floyd>   FAIL  : Input "floyd 3 0 34 7 34 0 -1 7 -1 0" did not produce output "0 34 7 34 0 41 7 41 0".  

floyd 4 0 -1 27 98 -1 0 41 74 27 41 0 41 98 74 41 0
0 -1 27 68 -1 0 41 74 27 41 0 41 68 74 41 0 
floyd>   FAIL  : Input "floyd 4 0 -1 27 98 -1 0 41 74 27 41 0 41 98 74 41 0" did not produce output "0 68 27 68 68 0 41 74 27 41 0 41 68 74 41 0".
4

1 に答える 1