文章

4

粉丝

238

获赞

4

访问

39.6k

头像
ProblemC,Dijkstra
P1631 上海交通大学2019年机试题
发布于2021年2月28日 18:44
阅读数 11.8k

 

题目既然是带权图,两点最短距离不一定是邻边,有可能要经过其他点

假如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,...,n}互相的最短距离(要么为原值要么为经过k的新值)并求和

N诺的测试样例不够,所以不少错误的也通过了,下面给出一个样例:

5
0 1 2 3 4
1 0 6 4 2
2 6 0 1 8
3 4 1 0 5
4 2 8 5 0

结果应该=80

//2019上交机试ProblemC 刘家奇 20210228
#include <iostream>
using namespace std;

const unsigned int MAX = -1;
int n;
unsigned int D[505][505]; //邻接矩阵 
bool final[505][505];
//依次将最大元素加入集合 

//返回k加入后k到已加入元素的最短距离和 
unsigned int Dij(int k){
	unsigned int sum = 0;
	int v;unsigned int minn;
	for(int i=0;i<n-k-1;i++){ //n-k-1条 
		minn=MAX;
		for(int j=k+1;j<n;j++){ 
			if(!final[k][j] && D[k][j]<minn){
				minn=D[k][j];
				v=j;
			}
		}
		sum+=minn;
		final[k][v]=final[v][k]=true;
		for(int j=k+1;j<n;j++){ //minn...
登录查看完整内容


登录后发布评论

1 条评论
admin SVIP
2021年2月28日 23:45

感谢提醒,数据已加强laugh

赞(0)