遍及组集训--图论最短路径设分层图

P4568 [JLOI2011] 飞行路线 - 洛谷 | 盘算机科学教诲新生态
  可以设置分层图：(伪代码）

1. E(u,v)=w;无向图
2. add(u,v,w),add(v,u,w);
3. for(j=1~k){
4.         add(u+jn,v+jn,w);
5.         add(v+jn,u+jn,w);
6.         add(u+jn-j,v+jn-j,0);
7.         add(v+jn-j,u+jn-j,0);
8. }

复制代码

add(u+jn-j,v+jn-j,0); add(v+jn-j,u+jn-j,0); 是从上面的节点到下面相对应的节点为0；因为有k此转程，且不可以或许重复经过某一结点。建图用链式前向星，最短路径不要用spfa，要用dijkstra，而且要堆优化。
真建图方式：

1. for(int i=0;i<m;i++){
2.        u=Read(),v=Read(),c=Read();
3.        add(u,v,c);
4.        add(v,u,c);
5.        for(int j=1;j<=k;j++){
6.            add(u+(j-1)*n,v+j*n,0);
7.            add(v+(j-1)*n,u+j*n,0);
8.            add(u+j*n,v+j*n,w);
9.            add(v+j*n,u+j*n,w);
10.        }
11. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。