当前位置:网站首页>AcWing 344. Solution to the problem of sightseeing tour (Floyd finding the minimum ring of undirected graph)
AcWing 344. Solution to the problem of sightseeing tour (Floyd finding the minimum ring of undirected graph)
2022-07-07 01:36:00 【Mr. Qiao Da】
AcWing 344. Sightseeing tour
Use this question floyd To find the minimum ring problem of undirected graphs , Pay attention to the sequence and significance of recording the path and finding the minimum intermediate point ( Because what is required is a ring , When you first find the ring , here k Not updated to i、j The shortest point between , So in path[cnt ++ ] = k And the next line get_min in path[cnt ++ ] = k Of k Values are different , It is guaranteed to be a ring )
#include<bits/stdc++.h>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int d[N][N], w[N][N]; //d Store the shortest path ,w Store edge weights
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); // find i And the middle point k And save path Array
path[cnt ++ ] = k;
get_path(k, j); // find k and j And save path Array
}
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 ++ ){
// What is more puzzling here is why to seek the path first , Find the shortest distance between two points
// as a result of , here k Not updated to i、j The shortest point between
// So in path[cnt ++ ] = k And the next line get_min in path[cnt ++ ] = k Of k Values are different , It is guaranteed to be a ring
// Find the path first
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]){
// Find a smaller ring
res = d[i][j] + w[k][i] + w[j][k]; // Pay attention to the direction of the ring
cnt = 0; // Re record the path
path[cnt ++ ] = k; // This ring is from k set out
path[cnt ++ ] = i;
get_path(i, j);
path[cnt ++ ] = j;
}
}
}
// Find the middle point
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;
}
边栏推荐
猜你喜欢
According to the analysis of the Internet industry in 2022, how to choose a suitable position?
Appium automation test foundation uiautomatorviewer positioning tool
黑马笔记---异常处理
Appium自动化测试基础 — uiautomatorviewer定位工具
一起看看matlab工具箱内部是如何实现BP神经网络的
Send template message via wechat official account
Make Jar, Not War
第三方跳转网站 出现 405 Method Not Allowed
从底层结构开始学习FPGA----FIFO IP的定制与测试
MySQL script batch queries all tables containing specified field types in the database
随机推荐
Vocabulary in Data Book
域分析工具BloodHound的使用说明
Make Jar, Not War
从零开始匹配vim(0)——vimscript 简介
Today's question -2022/7/4 modify string reference type variables in lambda body
拖拽改变顺序
Can the system hibernation file be deleted? How to delete the system hibernation file
C语言实例_4
今日问题-2022/7/4 lambda体中修改String引用类型变量
数据手册中的词汇
JS reverse -- ob confusion and accelerated music that poked the [hornet's nest]
1123. The nearest common ancestor of the deepest leaf node
Docker method to install MySQL
编译命令行终端 swift
1123. 最深叶节点的最近公共祖先
C language instance_ two
Amway wave C2 tools
修改px4飞控的系统时间
黑马笔记---创建不可变集合与Stream流
Long press the button to execute the function