AcWing 344. 观光之旅 蓝书实现
原题链接
中等
作者:
ㅤ_928
,
2023-12-06 16:23:59
,
所有人可见
,
阅读 58
Floay
$O(n^3)$
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 310;
const int INF = 0x3f3f3f3f;
int pos[N][N],dist[N][N],g[N][N];
int n,m;
vector<int> path;
void init(){
for(int i = 1;i<=n;i++) {
for(int j = 1;j<=n;j++)
if(i == j) g[i][j] = 0;
else g[i][j] = INF;
}
}
void get_path(int x,int y){ x到y的路径 不包括x和y
if(!pos[x][y]) return ;
get_path(x,pos[x][y]); 左半边
path.push_back(pos[x][y]); 中间点
get_path(pos[x][y] , y); 右半边
}
signed main()
{
cin >> n >> m;
init();
for(int i = 0;i<m;i++){
int a,b,w;cin >> a >> b >> w;
g[b][a] = g[a][b] = min(g[a][b] , w);
}
int ans = INF;
memcpy(dist,g,sizeof g);
for(int k = 1;k<=n;k++){
for(int i = 1;i<k;i++)
for(int j = i+1;j<k;j++)
if(dist[i][j] + g[j][k] + g[k][i] < ans){ 这里不开long long 的话如果是三个INF相加会爆int
ans = dist[i][j] + g[j][k] + g[k][i];
path.clear();
path.push_back(i);
get_path(i,j);
path.push_back(j);
path.push_back(k);
}
for(int i = 1;i<=n;i++)
for(int j = 1 ; j<=n;j++)
if(dist[i][j] > dist[i][k] + dist[k][j]){
dist[i][j] = dist[i][k] + dist[k][j];
pos[i][j] = k;
}
}
if(ans == INF) cout << "No solution." << endl;
else for(int i = 0;i<path.size();i++) cout << path[i] << " ";
return 0;
}
不是 Floyd 吗?
打错了 感谢提醒