如题= =自用模板

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;  
}