2019sjtuC-带权无向图问题

题意理解:给定一张带权无向图，依次从中拿走第i个点，求剩下的点到其他点的最短距离之和

分析问题：我们假设一张六个点的带权无向图，顶点编号0~5，按照题意我们可以得到所求：

• 拿掉0号点，求1,2,3,4,5分别到其他点的距离
• 拿掉1号点，求2,3,4,5分别到其他点的距离
• 拿掉2号点，求3,4,5分别到其他点的距离
• 拿掉3号点，求4,5分别到其他点的距离
• 拿掉4号点，求5分别到其他点的距离
• 拿掉5号点

我们倒着看分析过程：

• 拿掉5号点
• 拿掉4号点，求5分别到其他点的距离
• 拿掉3号点，求4,5分别到其他点的距离
• 拿掉2号点，求3,4,5分别到其他点的距离
• 拿掉1号点，求2,3,4,5分别到其他点的距离
• 拿掉0号点，求1,2,3,4,5分别到其他点的距离

可以发现，依托floyd算法，我们让k从n-1开始遍历，每对k进行一次floyd算法，再对k及更大的点的最短路径求和

最终答案的总和即为所求（画个图好理解）

#include <iostream>
#include <algorithm>

using namespace std;
const int N=510;
int mat[N][N];
int n;

int main()
{
    while(cin>>n)
    {   int res=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>mat[i][j];

        for(int k=n-1;k>0;k--){
            for(int i=0;i<n;i++)
                for(int j=i+1;j<n;j++)
                    if(mat[i][k]+mat[k][j]<mat[i][j])
                        mat[i][j]=mat[j][i]=mat[i][k]+mat[k][j];

            for(int m=k;m<n;m++)
                for(int t=m+1;t<n;t++)
                    res+=2*mat[m][t];
        }

        cout<<res<<endl;
    }
    return 0;
}

问题：为什么k不正向遍历：

因为如果正向遍历的话，举个例子：在删去0号点时，求解ans需要 借助了比k>0的点的最短路径，而此时k并未更新到位。

一句话，正向遍历时会用到还未更新的点，所以每删去一个点要更新一次dist数组！！

而反向遍历时，只需要比k更大的点更新，所以可以在一次floyd的过程中顺带求出ans，因此本题反向遍历。