lw

用户名：saudade

访问量：13790

签　名：

等　　级
排　　名	175
经　　验	6857
参赛次数	23
文章发表	25
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

得得得得得
浏览：249

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

[传智杯]传送门-题解(C++代码)--Floyd 欢迎大佬来指点

　　作者: lw　　　　发表时间：2020-04-19 11:26:30 浏览：1056　|　评论：1　

原题链接：[传智杯]传送门

## 比赛前第二天才写出来的，菜鸡赛后学的Floyd算法，太菜太菜，欢迎大佬来指点
下面是Floyd算法的核心语句，不会的话可以百度学一下
```cpp
for(k=1;k<=n;k++)  
    for(i=1;i<=n;i++)  
      for(j=1;j<=n;j++)  
           if(e[i][j]>e[i][k]+e[k][j])  
		          e[i][j]=e[i][k]+e[k][j];  
```
先用Floyd算法进行预处理一下，算出没有传送门时两点间的最短距离
```cpp
for(int k=1;k<=n;++k) {
		for(int i=1;i<=n;++i) {
			for(int j=i+1;j<=n;++j) {
				s[i][j]=min(s[i][j],s[i][k]+s[k][j]);
				s[j][i]=s[i][j];
			}
		}
	}
```
然后遍历所有的点对（i,j）,在i与j之间加上一个传送门，然后更新两点间的最短距离，由于i与j之间有传送门，所以两点之间的最短距离可以更新为：
dis[x][y]=min(dis[x][y],min(dis[x][i]+dis[j][y],dis[x][j]+dis[i][y]))
代码为：
```cpp
for(int i=1;i<=n;++i) {
		for(int j=i+1;j<=n;++j) {
			memcpy(t,s,sizeof(s));
			t[i][j]=0;
			t[j][i]=0;
			long long sum=0;
			for(int r=1;r<=n;++r) {
				for(int c=r+1;c<=n;++c) {
					sum+=min(t[r][c],min(t[r][i]+t[j][c],t[r][j]+t[i][c]));
				}
			}
			minn=min(sum,minn);
		}
	}
```
我这里是直接用sum加的
```cpp
#include<iostream>
#include<cstring>
using namespace std;
const int MAX=0x1fffffff;
int n,m;
int s[105][105];
int t[105][105];
int b,e,l;
long long minn=MAX;
int main()
{
	cin >> n >> m;
	for(int i=1;i<=n;++i) {
		s[i][i]=0;
		for(int j=i+1;j<=n;++j) {
			s[i][j]=MAX;
			s[j][i]=MAX;
		}
	}
	for(int i=0;i<m;++i) {
		cin >> b >> e >> l;
		s[b][e]=l;
		s[e][b]=l;
	}
	for(int k=1;k<=n;++k) {
		for(int i=1;i<=n;++i) {
			for(int j=i+1;j<=n;++j) {
				s[i][j]=min(s[i][j],s[i][k]+s[k][j]);
				s[j][i]=s[i][j];
			}
		}
	}
	for(int i=1;i<=n;++i) {
		for(int j=i+1;j<=n;++j) {
			memcpy(t,s,sizeof(s));
			t[i][j]=0;
			t[j][i]=0;
			long long sum=0;
			for(int r=1;r<=n;++r) {
				for(int c=r+1;c<=n;++c) {
					sum+=min(t[r][c],min(t[r][i]+t[j][c],t[r][j]+t[i][c]));
				}
			}
			minn=min(sum,minn);
		}
	}
	cout << minn << endl;
	return 0;
}
```
代码中有许多地方需要改进，欢迎大佬们提出建议

0.0分

17 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

JakeLin

写得很好

2020-04-20 20:37:31

lw

TA的其他文章

你可能喜欢

Hello, world! （Java代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

震宇大神的杀毒软件（C语言代码）

[传智杯]传送门-题解(C++代码)--Floyd 欢迎大佬来指点

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.1 （Java代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

lw

TA的其他文章

你可能喜欢

Hello, world! （Java代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

震宇大神的杀毒软件 （C语言代码）

[传智杯]传送门-题解(C++代码)--Floyd 欢迎大佬来指点

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.1 （Java代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题9.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

震宇大神的杀毒软件（C语言代码）

　　评论区