普及组集训--图论最短路径设分层图
可以设置分层图:(伪代码)
E(u,v)=w;无向图
add(u,v,w),add(v,u,w);
for(j=1~k){
add(u+jn,v+jn,w);
add(v+jn,u+jn,w);
add(u+jn-j,v+jn-j,0);
add(v+jn-j,u+jn-j,0);
}
add(u+jn-j,v+jn-j,0); add(v+jn-j,u+jn-j,0); 是从上面的节点到下面相对应的节点为0;因为有k此转程,且不能够重复经过某一结点。建图用链式前向星,最短路径不要用spfa,要用dijkstra,而且要堆优化。
真建图方式:
for(int i=0;i<m;i++){
u=Read(),v=Read(),c=Read();
add(u,v,c);
add(v,u,c);
for(int j=1;j<=k;j++){
add(u+(j-1)*n,v+j*n,0);
add(v+(j-1)*n,u+j*n,0);
add(u+j*n,v+j*n,w);
add(v+j*n,u+j*n,w);
}
}
原文地址:https://blog.csdn.net/2301_78836126/article/details/144318527
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!