一看就是求最小环，但是构图非常恶心。按照我朴素的思维方式，想了N天N夜，想到了利用BFS（或DFS）给定点标号，然后在建边的算法。
时空复杂度理论上都是很好的。但今天一上机就怂了，因为编程复杂度太大。又思考了一段时间无解之后，我求助于NOCOW。
了解了一种把边看作点，然后给边直接连上“边”的算法。实际操作中也遇到一些困惑，这里就不提了，主要是floyd算法的细节要注意。
我对该算法的细节认识：
1.k在外循环，只有前k个点是更新完的。
2.Infinity 不能取太大，会爆的。
具体的注释在代码中了
代码
/*
USER:zyn19961
LANG:C++
TASK:fence6
*/
#include<cstdio>
#include<cstring>
const int INF=1<<25;//不能取太大
int n,a[200][200],b[200][200],l[200],left[200][200],right[200][200];
int inline min(int a,int b){return a<b?a:b;}
int s,ans;
int main()
{
freopen("fence6.in","r",stdin);
freopen("fence6.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=INF;
for(int i=1;i<=n;i++){
scanf("%d",&s);
scanf("%d",&l[s]);
scanf("%d %d",&left[s][0],&right[s][0]);
for(int j=1;j<=left[s][0];j++)
scanf("%d",&left[s][j]);
for(int j=1;j<=right[s][0];j++)
scanf("%d",&right[s][j]);
}
//边->点 转化
for(int i=1;i<=n;i++){
for(int j=1;j<=left[i][0];j++)
a[i][left[i][j]]=l[i]+l[left[i][j]];//取两边的边长和作为两边之间“边”的权值
for(int j=1;j<=right[i][0];j++)
a[i][right[i][j]]=l[i]+l[right[i][j]];
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
b[i][j]=a[i][j];//a为i，j间的最短路，b为边权.
//
ans=INF<<4;
for(int k=1;k<=n;k++){//经过k点
for(int i=1;i<=left[k][0];i++){//向左
int x=left[k][i];//只是写起来方便而已，下同
if(x<k){//只能更新前k-1个点换
for(int j=1;j<=right[k][0];j++){//向右
int y=right[k][j];
if(y<k)//只能更新前k-1个点之间的环
ans=min(ans,a[x][y]+b[k][x]+b[k][y]);
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
printf("%d\n",ans/2);//这个显然
fclose(stdin);
fclose(stdout);
return 0;
}
关于代码最后输出 显然的结论的说明:
在一个环中，每条边经过一次，且首尾相接。
这个环上的“边”连接这图中的边集中的两个边，
且每条边恰好被连接两次.故ans要/2