社区讨论

求助初赛

学术版参与者 3已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
6 条
当前快照
1 份
快照标识符
@lo21vwas
此快照首次捕获于
2023/10/23 06:38
2 年前
此快照最后确认于
2023/11/03 07:00
2 年前
查看原帖
CPP
//小兔岭上刷到的初赛题,有没有哪位大佬告诉我第二个floyd干什么用的?
#include<cstdio> 
2       #include<cstring>
3	using namespace std;
4 	int n, m; 
5	int f[101][101];
6 	intF[101][101]; 
7	int main(){ 
8 	scanf("%d%d",&n,&m);//n的值在1到100之间 
9 	memset(f,-1sizeof(f)); 
10 	for(int i = 1; i <=  m; i++) { 
11 		int u,v,w;//w的值在0到10000之间 
12 		scanf("%d%d%d",&u,&v,&w); 
13 		f[u][v]=f[v][u]=w; 
14	}
15 	for(int k = 1; k <= n; k++) 
16 		for(int i=1;i <=n; i++) 
17 			for(int j=1;j<= n; j++) 
18 				if(f[i][k]!=-1&&f[k][j]!=-1) 
19 					if(f[i][j]==-1||f[i][j]>f[k][j]+f[i][k]) 
20 						f[i][j]=f[i][k]+f[k][j]; 
21 	int ans=2147483647; 
22 	for(int i=1;i<=n;i++) 
23 		for(int j=1;j<=n; j++){ 
24 			for(int x=1;x<=n; x++) 
25 				for(int y=1;y<=n; y++) 
26 					F[x][y]=f[x][y]; 
27 			F[i][j]=F[j][i]=0; 
28 			for(int x=1;x<= n; x++) 
29 				for(int y=1;y<=n; y++) 
30 					if(F[x][y]==-1||F[x][y]>F[x][i]+F[i][y]) 
31 						F[x][y]=F[x][i]+F[i][y]; 
32 			for(int x=1;x<=n; x++) 
33 				for(int y=1;y<=n; y++) 
34 					if(F[x][y]==-1||F[x][y]>F[x][j]+F[j][y]) 
35 						F[x][y]=F[x][j]+F[j][y]; 
36 			int res=0; 
37 			for(int x=1;x<=n; x++) 
38 				for(int y=1;y<x; y++) 
39 					res +=F[x][y]; 
40 			ans=min(res,ans); 
41			}
42 	printf("%d\n",ans); 
43 	return 0; 
44 	}	

回复

6 条回复,欢迎继续交流。

正在加载回复...