这个Floyd-Warshall实现中的错误是什么？

Question

下面是问题链接：http://codeforces.com/contest/295/problem/B

Greg有一个加权有向图，由n个顶点组成。在这个图中，任何一对不同的顶点在它们之间的两个方向上都有一条边。Greg喜欢玩图表，现在他发明了一个新游戏：

这个游戏由n步组成。在第i步，Greg从图中删除顶点编号xi。当Greg移除一个顶点时，他也会移除进出该顶点的所有边。在执行每一步之前，Greg想知道所有剩余顶点对之间的最短路径的长度总和。最短路径可以通过任何剩余的顶点。帮助Greg，在每一步之前打印出所需和的值。

输入：

第一行包含整数n (1 ≤ n ≤ 500) -图形中的顶点数。

接下来的n行每行包含n个整数-图邻接矩阵:第i行aij (1 ≤ aij ≤ 105， aii = 0)中的第j个数字表示从顶点i到顶点j的边的权重。

下一行包含n个不同的整数: x1， x2， ...， xn (1 ≤ xi ≤ n) - Greg删除的顶点。

输出：

打印n个整数-第i个数字等于第i步之前所需的总和。

因此，基本上我的方法是在删除任何顶点之前运行弗洛伊德-沃肖尔算法，对于删除，我只需在行和列的邻接矩阵中将要删除的顶点的值设置为INT_MAX。

基本上，这个循环是在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;
    }

这是我对Flloyd 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是我设置为全局的3-D矩阵，而arr包含要删除的顶点。然而，当我运行这个逻辑时，它只在最初给出正确的答案，即没有顶点被删除时。但是在那之后，它给出了一个错误的值。我不明白为什么？我的逻辑是错误的吗？

Answer 1

看起来很奇怪的一件事是，在结束时，你需要计算所有剩余顶点对的和，但你的循环只是在所有顶点上：

for ( i = 1; i <= n; i++ )
    for ( j = 1; j <= n; j++ )
        ans = ans + val[i][j][n];

Answer 2

这是错误的方式，将得到TLE....沿着这条路走

你应该牢记对floyd warshall算法的良好理解。

首先弄清楚你自己，然后到这一点，在这个算法中，你可以按任何顺序设计你的中间元素(k)。下面是n个步骤，这意味着n个节点将以给定的顺序……被删除这意味着在这个给定的顺序中，你可以设计你的中间元素。假设给定的删除顺序集是1，2，3……………。。

现在这意味着当一个顶点将被删除时，那么每对最短路径的总和。然后，当2也被删除时，然后依此类推………

现在这样想，当只考虑所有顶点都被删除而没有3的时候，这里使用k(3) u可以在只剩下3的时候求和，现在使k的值是(2 )，这意味着只有2和3是剩余的，其他的都被删除了，现在使和……..So如果你颠倒了这个答案，当剩余1 2 3时，则求和(没有删除顶点)，然后删除1

这意味着剩下的只有2，3被删除，使它们的总和为………。

因此，我认为如果你对floyd warshall算法有很好的想法，这一点应该很清楚。

我的整洁的解决方案就是基于上面的想法。

https://github.com/joy-mollick/Problem-Solving-Solutions/blob/master/Codeforces-B%20-%20Greg%20and%20Graph.cpp