如题= =自用模板
floyd求最小环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int floyd() {  
int ans=0x1f1f1f1f;
for(int i=1;i<=n;++i)
for(int j=i;j<=n;++j)
dis[i][j]=dis[j][i]=g[i][j];

for(int k=1;k<=cnt;++k) {
for(int i=1;i<k;++i)//寻找最小环 i,j,k
for(int j=i+1;j<k;++j)
if(dis[i][j]+g[i][k]+g[k][j]<ans)//由于此处会存在三个INF相加,所以INF设为0x1f1f1f1f
ans=dis[i][j]+g[i][k]+g[k][j];

for(int i=1;i<=n;++i)//更新最短路
for(int j=1;j<=n;++j)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
return ans;
}