floyd求。
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
for(int j=1;j<k;j++)
ans=min(ans,dis[i][k]+dis[k][j]+map1[j][i])
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j])
}
看似最好写的代码,实际上最不容易理解。
上面代码有向无向都通用。
令k为最小环中最大的节点,所以i j只需要枚举到k-1,后面的都是冗余的。有向图注意标号,无向图无所谓。
重点在于k是最大标号,先求最小环,再松弛,否则k可能成为中间节点
比如
3一定要先更新最小环,再被松弛。
最小环中的路径在 更新的时候一定要保证路径上的点的标号严格小于k,其实是不等于k
有向图也可以先求floyd最短路。
然后枚举边u v ans=min(ans,map1[u][v]+dis[v][u])