今天写了一道图论题，题解有一种就是使用分层图求最短路的算法
但是我这里只是想说一下分层图建立关系的问题，并不是写题解和算法过程
链接 http://acm.hdu.edu.cn/showproblem.php?pid=3499
按照题意我们只有一次使用减半价格的机会，所以对于这道题层数的只有两层
假设 从 u 点到 v 点的权值为 w
可以推出
这里我是使用邻接表存点，代码如下
1 const int N=100005; 2 const int M=500005; 3 int head[N<<2+1],to[M],nex[M],val[M],cnt=0; 4 inline void add(int s,int ed,int w) 5 { 6 to[++cnt]=ed;//u-->v 原边 7 val[cnt]=w; 8 nex[cnt]=head[s]; 9 head[s]=cnt; 10 11 to[++cnt]=ed+n;//u-->v+n 连接到下层图 费用减少 12 val[cnt]=w/2; 13 nex[cnt]=head[s]; 14 head[s]=cnt; 15 16 to[++cnt]=ed+n;// u+n-->v+n 下层图两点相连 17 val[cnt]=w; 18 nex[cnt]=head[s+n]; 19 head[s+n]=cnt; 20 }
我们每建一层图，我们对应的点的位置需要向后移动n个，因此需要注意 数组范围
原文：https://www.cnblogs.com/Snowindfly/p/11420900.html