floyd求最小环

https://www.cnblogs.com/Yz81128/archive/2012/08/15/2640940.html

在上方链接的基础上加了自己的理解，有误的话请指出。

floyd不断以某个点更新两个点之间的最小距离
因为至少三个点，又是求最小距离的环，将其记录为三个相邻主点i,k,j，表示一个环中相邻的三个点，则环长包括该相邻三点之间的直接距离mp[i][k],mp[k][j],以及可优化的距离d[i][j]。
此处需要保证优化后的距离d[i][j]不经过k;否则会出现如下图，应该是1+1+100而变成了1+1+2的场景。
所以选择在对k进行最短更新前先计算以k为中心，并且相邻两点i,j都比k小，的所有环的最短距离。（这样可以保证d[i][j]还没有用k进行更新，所以不经过k）然后再用k更新d表(此时d[i][j]才可能经过k)。

一直到你更新到所求环中，标号最大的节点k0，时，此时比k0小的最短路径已经全部更新，则一定可以求出你所求的环。反正要以k0为中心，遍历所有比他小的节点，k0在环中，则一定能够遍历到。
以下是代码，如有问题请指出一起讨论，我也是在理解别人的基础上进行自己的加工。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int mp[110][110];
int d[110][110]; 
	int ans;
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<k;i++){
			for(int j=1;j<k;j++){//相等时不能往回更新，这样并没有经过三个点 
				if(i==j)continue;
				ans=min(ans,d[i][j]+mp[i][k]+mp[k][j]);  //经过三个点肯定有两条直连线啊
				                                        //需要保证d[i][j]这个最短路径不经过k，所以先计算ans，再用k更新最短路径 
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
			}
		}
	}
}
int main(){
	cin>>n>>m;
	fill(mp[0],mp[0]+110*110,1e5+1);
	fill(d[0],d[0]+110*110,1e5+1);
	ans=1e5+1;
	for(int ii=0;ii<m;ii++){
		int a1,a2,a3;cin>>a1>>a2>>a3;
		int mi=min(mp[a1][a2],a3);
		mp[a1][a2]=mi;mp[a2][a1]=mi;
		d[a1][a2]=mi;d[a2][a1]=mi;
	}
	
//	for(int u=1;u<=n;u++){	for(int v=1;v<=n;v++){		cout<<setw(7)<<mp[u][v];	}cout<<endl;	}
	floyd();
	if(ans!=1e5+1)cout<<ans;
	else cout<<"No solution.";
//		for(int u=1;u<=n;u++){	for(int v=1;v<=n;v++){	cout<<setw(7)<<mp[u][v];	}cout<<endl;	}
}

/*
	for(int k=1;k<=n;k++){
		for(int i=1;i<k;i++){
			for(int j=i+1;j<k;j++){//i j都小于k 
				ans=min(d[i][j]+mp[i][k]+mp[k][j],ans);//所以d[i][j]为不经过 大于等于k节点的  i到j最短距离 
				                                       // 加上只经过 k和比k小的节点  的最短距离 
			}
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){ //然后以k终中介点更新表，此时所有的最短路径可以经过k，但是已经不会计算k 为中心的最小环了 
			d[i][j] =min(d[i][j],d[i][k]+d[k][j]);d[j][i]=d[i][j];
		}
	}	
  }
*/