floyd中第一层循环k是指，从i到j中，编号最大的点为k！
flyd记录方案数的方法为：存一个pos数组，po[i][j]=k,更新ij的点为k，然后做一个递归
输出更新i~k的，再输出更新k~j的
#include <iostream>
#include <cstring>
using namespace std;
const int N=110,M=100100;
int g[N][N],path[N],pos[N][N];
int dist[N][N];
int cnt;
int n,m;
void get_path(int i,int j)
{
//如果i和j直接没有点
if(pos[i][j]==0) return;
int k=pos[i][j];
get_path(i,k);
path[cnt++]=k;
get_path(k,j);
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i=1;i<=n;i++)
{
g[i][i]=0;
}
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
memcpy(dist,g,sizeof dist);
int res=0x3f3f3f3f;
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
if((long long)dist[i][j]+g[j][k]+g[k][i]<res)
{
res=dist[i][j]+g[j][k]+g[k][i];
cnt=0;
//第一个点为k，第二个点为i，然后接下来的点是i到j的点
path[cnt++]=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(dist[i][j]>dist[i][k]+dist[k][j])
{
pos[i][j]=k;
dist[i][j]=dist[i][k]+dist[k][j];
}
}
}
}
if(res==0x3f3f3f3f) cout<<"No solution.";
else
for(int i=0;i<cnt;i++)
cout<<path[i]<<" ";
return 0;
}
二刷
pos记为pos[i,j]=k,s更新ij是由k转移过来的
注意get_path的递归写法：递归找中间点
#include <iostream>
#include <cstring>
using namespace std;
const int N=110,M=10010;
int g[N][N],dist[N][N],pos[N][N];
int n,m;
int cnt;
int path[N];
void get_path(int i,int j)
{
//如果i和j直接没有点
if(pos[i][j]==0) return;
int k=pos[i][j];
get_path(i,k);
path[cnt++]=k;
get_path(k,j);
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i=1;i<=n;i++)
{
g[i][i]=0;
}
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
memcpy(dist,g,sizeof dist);
int res=0x3f3f3f3f;
//floyd:从i到j，经过最大编号为k的点的最短距离
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
//找最小环
if((long long)dist[i][j]+g[j][k]+g[k][i]<res)
{
res=dist[i][j]+g[j][k]+g[k][i];
cnt=0;
//第一个点为k，第二个点为i，然后接下来的点是i到j的点
path[cnt++]=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++)
{
//大于号右侧为经过k的最短路径，大于号左侧为不经过k的最短路径
if(dist[i][j]>dist[i][k]+dist[k][j])
{
dist[i][j]=dist[i][k]+dist[k][j];
pos[i][j]=k;
}
}
}
}
if(res==0x3f3f3f3f) cout<<"No solution.";
else
for(int i=0;i<cnt;i++)
cout<<path[i]<<" ";
return 0;
}
三刷，又遇到了新坑
- get_path函数中，
path[++cnt]=k;要放在中间，不能放在前面
再次总结一下思路：
1. 做floyd时，最外层循环为：从i到j，经过最大编号为k的点的最短距离
2. 在每一层k中，找一次最小环，若有更小的则更新
3. 先更新最小环，最小环从k开始，经过的边为k->i, i..->…->j,j->k
4. 再更新距离dist[i][j]，如果更新了，则要记录更新dist[i][j]的点k
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N=2010;
int dist[N][N],g[N][N],path[200010];
int st[N];
int n,m;
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);
path[++cnt]=k;
get_path(k,j);
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i=1;i<=m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);
}
memcpy(dist,g,sizeof dist);
int res=0x3f3f3f3f;
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
if((long long)dist[i][j]+g[j][k]+g[k][i]<res)
{
//找到一个新的最小环，更新组成它的点
res=dist[i][j]+g[k][i]+g[j][k];
cnt=0;
path[++cnt]=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(dist[i][j]>dist[i][k]+dist[k][j])
{
dist[i][j]=dist[i][k]+dist[k][j];
pos[i][j]=k;
}
}
}
}
if(res>=0x3f3f3f3f) cout<<"No solution.";
else
for(int i=1;i<=cnt;i++)
{
cout<<path[i]<<" ";
}
return 0;
}
