P1631 上交2019 Problem C - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2022年3月24日 11:54

floyd算法 O(n^3)

P1631

回复 2 | 赞 4 | 浏览 6.2k

在Floyd算法更新最短路径的同时，更新最短路径之和 #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int num; cin>>num; int ans = 0; int ** mpt = new int* [num]; for(int i = 0; i < num; i ++){ mpt[i] = new ...

2020年3月22日 21:42

P1631

回复 2 | 赞 1 | 浏览 13.3k

又是一个签到题。尤其时无向图，由于其对称性，该题就十分简单了。无非就是把权值为非0的边，按次数加起来就行了。比如，二维数组第二行，代表结点2，考虑先删除第一点，该行加一次就行了。最后一行就需要加n-1次。实际上就是个数组按行*权值相加，没啥好说的。 #include<iostream> using namespace std; int main(){ int n; while(cin>>n){ int sum = 0; int a[n+1][n+1]; for(...

2021年2月28日 22:50

Floyd算法，不难

P1631

回复 1 | 赞 0 | 浏览 10.7k

复杂度到了n^4，懒得优化了。 #include<iostream> #include<algorithm> using namespace std; int len; int A[501][501]; int main(){ int len; cin>>len; int A[len][len]; for(int i=0; i<len; i++){ for(int j=0; j<len; j++) cin>>A[i][j]; } int res = 0; for(int ...

2021年2月28日 18:44

ProblemC,Dijkstra

P1631

回复 1 | 赞 3 | 浏览 12.2k

题目既然是带权图，两点最短距离不一定是邻边，有可能要经过其他点假如4-5的最短距离要经过2，拿掉2之后4-5的最短距离会变化看到一种精简写法，每拿掉一点，对剩下图用floyd刷新一次统计一次，是暴力计算，总复杂度达到O(n^4) 此题为动态图，每加一次点，只需Dij(k)一次O(n^2)，再以k为中间点刷新一次O(n^2)，加n-1个点，总复杂度O(n^3) 初始集合为元素n,集合依次加入n-1,n-2,...,2 元素k加入集合时，Dij(k)更新k到k+1,...,n的最短距离并求和再更新原集合{k+1...

题目上交2019 Problem C

题解数量4

热门题解

1 floyd算法 O(n^3)

2 ProblemC,Dijkstra

3 数组求和

4 Floyd算法，不难