ここに問題のリンクがあります: http://codeforces.com/contest/295/problem/B
Greg には、n 個の頂点からなる加重有向グラフがあります。このグラフでは、異なる頂点の任意のペアの間に、両方向のエッジがあります。Greg はグラフで遊ぶのが大好きで、今では新しいゲームを発明しました。
ゲームは n ステップで構成されます。i 番目のステップで、Greg は頂点番号 xi をグラフから削除します。Greg が頂点を削除すると、この頂点に出入りするすべてのエッジも削除されます。各ステップを実行する前に、Greg は残りの頂点のすべてのペア間の最短経路の長さの合計を知りたいと考えています。最短パスは、残りの頂点を通過できます。グレッグを助けて、各ステップの前に必要な合計の値を出力してください。
入力：
最初の行には、整数 n (1 ≤ n ≤ 500) — グラフ内の頂点の数が含まれています。
次の n 行には、それぞれ n 個の整数が含まれます — グラフ隣接行列: i 行目の j 番目の数値 aij (1 ≤ aij ≤ 105、aii = 0) は、頂点 i から頂点 j に向かうエッジの重みを表します.
次の行には、n 個の異なる整数が含まれています: x1、x2、...、xn (1 ≤ xi ≤ n) — Greg が削除する頂点。
出力：
n 個の整数を出力 — i 番目の数値は、i 番目のステップの前に必要な合計に等しくなります。
INT_MAXしたがって、基本的に私のアプローチは、頂点を削除する前に Floyd-Warshall アルゴリズムを実行することでした。削除するには、行と列の両方の隣接行列のように、削除する頂点の値を設定するだけです。
基本的に、このループはmain
for (int h = 0; h < n; h++)
{
func();
int val = arr[h]; // arr contains the vertices to be deleted
for ( i = 1; i <= n; i++ )
dist[val][i] = INT_MAX;
for ( i = 1; i <= n; i++ )
dist[i][val] = INT_MAX;
}
これは、Floyd Warshall アルゴリズムの私の実装です。
void func ()
{
//int i,j,k;
ans = 0;
for ( i = 1; i <= n; i++ )
{
for ( j = 1; j <= n; j++ )
{
if (i == j)
val[i][j][0] = 0;
else if (dist[i][j] != 0)
val[i][j][0] = dist[i][j];
else
val[i][j][0] = INT_MAX;
}
}
for (k = 1; k <= n; k++)
for ( i = 1; i <= n; i++ )
for ( j = 1; j <= n; j++ )
val[i][j][k] = min(val[i][j][k-1],val[i][k][k-1]+val[k][j][k-1]);
//int ans = 0;
for ( i = 1; i <= n; i++ )
for ( j = 1; j <= n; j++ )
ans = ans + val[i][j][n];
cout<<ans<<"\t";
}
valこれは、グローバルに作成した 3D マトリックスで、arr削除する頂点が含まれています。ただし、このロジックを実行すると、正しい答えが得られるのは最初だけです。つまり、頂点が削除されていないときです。しかし、その後、間違った値が返されます。なぜだか分からない？私の論理は間違っていますか？