当前位置:网站首页>AcWing 344. 观光之旅题解(floyd求无向图的最小环问题)
AcWing 344. 观光之旅题解(floyd求无向图的最小环问题)
2022-07-06 18:00:00 【乔大先生】
AcWing 344. 观光之旅
这题是利用floyd的性质求无向图的最小环问题,注意记录路径和求最小中间点的先后顺序和顺序的意义(因为要求的是环,先求环的时候,此时k还未更新成i、j之间最短的点,所以在path[cnt ++ ] = k和下一行的get_min中path[cnt ++ ] = k的k值不同,保证了是一个环)
#include<bits/stdc++.h>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int d[N][N], w[N][N]; //d储存最短路径,w储存边权值
int path[N];
int pos[N][N];
int cnt;
void get_path(int i, int j){
if(pos[i][j] == 0) return ;
int k = pos[i][j];
get_path(i, k); //找到i和中间点k之间经过的点并存入path数组中
path[cnt ++ ] = k;
get_path(k, j); //找到k和j之间经过的点并存入path数组中
}
signed main()
{
cin>>n>>m;
memset(w, 0x3f, sizeof w);
for(int i = 1; i <= n; i ++ ) w[i][i] = 0;
while(m -- ){
int a, b, c;
cin>>a>>b>>c;
w[a][b] = w[b][a] = min(w[a][b], c);
}
int res = INF;
memcpy(d, w, sizeof d);
for(int k = 1; k <= n; k ++ ){
//这里比较疑惑的是为什么先求路径,再找两点之间最短距离
//原因是,此时k还未更新成i、j之间最短的点
//所以在path[cnt ++ ] = k和下一行的get_min中path[cnt ++ ] = k的k值不同,保证了是一个环
//先求路径
for(int i = 1; i < k; i ++ ){
for(int j = i + 1; j < k; j ++ ){
if(res > (long long)d[i][j] + w[k][i] + w[j][k]){
//找到更小环
res = d[i][j] + w[k][i] + w[j][k]; //注意按照环的方向
cnt = 0; //重新记录路径
path[cnt ++ ] = k; //这个环是从k出发
path[cnt ++ ] = i;
get_path(i, j);
path[cnt ++ ] = j;
}
}
}
//求中间点
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= n; j ++ ){
if(d[i][j] > d[i][k] + d[k][j]){
d[i][j] = d[i][k] + d[k][j];
pos[i][j] = k;
}
}
}
}
if(res == INF) cout<<"No solution."<<endl;
else{
for(int i = 0; i < cnt; i ++ ) cout<<path[i]<<' ';
cout<<endl;
}
return 0;
}
边栏推荐
- 图片打水印 缩放 和一个输入流的转换
- Analysis of mutex principle in golang
- Metauniverse urban legend 02: metaphor of the number one player
- JTAG principle of arm bare board debugging
- golang中的atomic,以及CAS操作
- 2022 Google CTF SEGFAULT LABYRINTH wp
- C language - array
- 公钥\私人 ssh避password登陆
- Oracle: Practice of CDB restricting PDB resources
- NEON优化:log10函数的优化案例
猜你喜欢
405 method not allowed appears when the third party jumps to the website
免费白嫖的图床对比
Clickhouse fields are grouped and aggregated, and SQL is queried according to the granularity of any time period
Make Jar, Not War
Force buckle 1037 Effective boomerang
1123. 最深叶节点的最近公共祖先
修改px4飞控的系统时间
第三方跳转网站 出现 405 Method Not Allowed
AI 从代码中自动生成注释文档
Analysis of mutex principle in golang
随机推荐
Atomic in golang and CAS operations
JS reverse -- ob confusion and accelerated music that poked the [hornet's nest]
AI 从代码中自动生成注释文档
增加 pdf 标题浮窗
Spark TPCDS Data Gen
黑马笔记---创建不可变集合与Stream流
Instructions for using the domain analysis tool bloodhound
[signal and system]
How to manage distributed teams?
Implementation principle of waitgroup in golang
LeetCode:1175. 质数排列
C语言实例_2
修改px4飞控的系统时间
Table table setting fillet
安全保护能力是什么意思?等保不同级别保护能力分别是怎样?
Sword finger offer II 035 Minimum time difference - quick sort plus data conversion
C language instance_ five
子网划分、构造超网 典型题
1123. The nearest common ancestor of the deepest leaf node
免费白嫖的图床对比