题目

{% raw %}

点击显/隐题目

{% endraw %} 小黄发明了一个图的游戏, 游戏在一个n个节点的有向有边权的完全图上进行:

游戏一共有n个步骤
在第i步, 小黄从图中移除掉一个节点以及与该节点相连的所有入边和出边(移除后的图仍然是一个完全图)
在每一步小黄移除一个节点之前, 他想知道所有节点对之间的最短路径的总和是多少

{% raw %}

{% endraw %}

输入为小黄游戏之前的图:
第一行: n(1<=n<=400), 表示图的节点个数;
接下来一共n行为一个n*n的矩阵, 矩阵的每行n个数, 第i行的第j列的数字a(1≤a≤?50000表示从节点i到节点j的边的边权, 其中节点i到节点i自身的边权都是0;
最后n行一行一个1到n之间的数, 其中的第i行表示第i步小黄要移除的节点编号.

{% raw %}

{% endraw %}

输出一共一行n个数(一个空格隔开), 分别为第i步移除节点之前的所有节点对的最短路径总和.

{% raw %}

{% endraw %}

4
0 3 1 1
6 0 400 1
2 4 0 1
1 1 1 0
4 1 2 3

{% raw %}

{% endraw %}

17 23 404 0

{% raw %}

{% endraw %}

题解

很好的一道题,算法是很简单的算法,但是需要有一定的理解

Floyd 是一个很容易被忽视的算法,因为它实在是太简单了
只需要三个循环就能完成多源最短路
尽管时间复杂度较高,但是多源最短路也没有其他更好的算法了

其本质是动态规划
以

for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);

为例
i 和 j 只是为了便利整个图,不属于动态规划的算法部分
重点看 k
这就是精华所在, k 的意义为,前 k 个点的最短路
那么,答案已经出来了,将删点看作加点,按照删除的逆序把点加入到图中,每次都只需要计算已经加入到图中的点的最短路和

在 Floyd 上已经坑过两次了,最简单的反而最容易忽视
比赛的时候已经想到了删点变为加点,不过没有细想 k 的意义,最后每加一个点都跑一次 Floyd 果断超时
想了只更新新加的点可能影响到的部分,还是基础功不扎实的锅

代码

点击显/隐代码

```cpp 最短路径和 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 /*/ #define debug #include //*/ #include #include #include #include using namespace std;

const int maxn = 405;
const int INF = 0x3f3f3f;
int del[maxn];
int dis[maxn][maxn];
int ans[maxn];

int main(){
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);

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

    for(int p=0;p<n;p++){
        cin >> del[p];
        del[p]--;
    }
        

    for(int p=n-1;p>=0;p--){
        int k = del[p];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                    dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);

        // cout << endl;
        // for(int i = 0;i < n;i++){
        //     for(int j = 0;j < n;j++)
        //         cout << dis[i][j] <<" ";
        //     cout << endl;
        // }
        // cout << endl;
        

        ans[p] = 0;
        for(int i=p;i<n;i++)
            for(int j=p;j<n;j++)
                    ans[p] += dis[del[i]][del[j]];
    }
    for(int i=0;i<n;i++){
        if(i)
            cout << " ";
        cout << ans[i];
    }
    cout << endl;
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;

}

</div>

AOJ 841.最短路径和

题目

题解

代码