AOJ 841.最短路径和

178


题目


点击显/隐题目

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

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




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





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





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





17 23 404 0





题解



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

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]);

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

在 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.syncwithstdio(false);

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

for(int p=0;pcin >> del[p];
del[p]--;
}


for(int p=n-1;p>=0;p--){
int k = del[p];
for(int i=0;ifor(int j=0;jdis[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;ifor(int j=p;jans[p] += dis[del[i]][del[j]];
}
for(int i=0;iif(i)
cout << " ";
cout << ans[i];
}
cout << endl;
}

#ifdef debug
printf("Time:%.3fs.n", double(clock() - START) / CLOCKSPERSEC);
#endif
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论