lw

用户名：saudade

访问量：12608

签　名：

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

　　自我简介：

TA的其他文章

得得得得得
浏览：220

你可能喜欢

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

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

　　作者: lw　　　　发表时间：2020-04-19 11:26:30 浏览：957　|　评论：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编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

JakeLin

写得很好

2020-04-20 20:37:31

lw

TA的其他文章

你可能喜欢

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

字符逆序（C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C二级辅导-等差数列（C语言代码）

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

评论区

精彩推荐

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

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

字符串的输入输出处理（C语言代码）

用筛法求之N内的素数。（C语言代码）

Hello, world! （C++代码）

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

打印十字图（C语言代码）

图形输出（C语言代码）

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

C二级辅导-分段函数（C语言代码）

lw

TA的其他文章

你可能喜欢

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

字符逆序 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言训练-求PI* （C语言代码）（正确结果竟然是谜一样的3.141591）

C二级辅导-等差数列 （C语言代码）

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

评论区

精彩推荐

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

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

字符串的输入输出处理 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

Hello, world! （C++代码）

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

打印十字图 （C语言代码）

图形输出 （C语言代码）

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

C二级辅导-分段函数 （C语言代码）

字符逆序（C语言代码）

C二级辅导-等差数列（C语言代码）

　　评论区

字符串的输入输出处理（C语言代码）

用筛法求之N内的素数。（C语言代码）

打印十字图（C语言代码）

图形输出（C语言代码）

C二级辅导-分段函数（C语言代码）