简谈分层图

分层图是一个处理对边存在额外操作的较好的处理方式。
这里引入一道例题，在正常的最短路中，你可以挑选k条路不需要花费时间，那么最小总花费是多少？
存在一种$dp$的处理方式，$dp[i][j]$表示到第i个节点用了j次免费，$dp[n][0k]$即为答案。
那么怎么去转移呢，$dp[v][j]=min(dp[u][j-1],dp[u][j]+u->v)$
我们可以把其转换成k+1个图，分别代表用了几次免费机会的图，并且免费是不断用的次数增加的，也就是说第$i$个图和第$j$个图有单向边相连，边权为0，代表用了一次免费机会。
如何去添加这些边呢，就是将$i->j$在每张图都加上，同时$i->j+n$也加上(同样在每张图)。
这里我用$((k-1)n+1->kn)$表示第$k$层的节点。
简要模板如下：

int n,m,k;
const int maxn = 10000000;
const int maxm = 20000000;
struct Edge{int from,to;ll dist;Edge(){}Edge(int _from,int _to,ll _dist):from(_from),to(_to),dist(_dist){}
};
Edge ed[maxm];int he[maxn],ne[maxm],etop=1;
void insert(int u,int v,ll w){ed[etop]=Edge(u,v,w);ne[etop]=he[u];he[u]=etop++;}void add_edge(int u,int v,ll w){for(int i=u,j=v;i<=u+k*n;i+=n,j+=n)insert(i,j,w);for(int i=u,j=v+n;j<=v+k*n;i+=n,j+=n)insert(i,j,0);
}ll d[maxn];
bool vis[maxn];
priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > q;
void dijkstra(int s){memset(vis,0,sizeof(vis));memset(d,0x3f,sizeof(d));d[s]=0;q.push(make_pair(0, s));while(!q.empty()){int now = q.top().second;q.pop();if(!vis[now]){vis[now] = true;for(int i = he[now]; i; i = ne[i]){Edge& e = ed[i];if(d[e.to] > d[now] + e.dist){d[e.to] = d[now] + e.dist;q.push(make_pair(d[e.to], e.to));}}}}
}

代码很简单，就是加上了边，所以分层图只是一种思想，没必要死记硬背。
但是这样的代码会$mle$,主要在于大量使用了一些不必要的点和边。
其实每次我们只需要对相邻层进行转移即可，其他都可以映射到初始图进行。
用$d[i][p]$表示到第$i$个点，使用了$p$次免费机会。
每次松弛的时候，对同一层松弛，同时判断是否还有免费机会，如果有，对下一层也松弛。

int n,m,k;
const int maxn = 100000;
const int maxm = 400010;
struct Edge{int from,to;ll dist;Edge(){}Edge(int _from,int _to,ll _dist):from(_from),to(_to),dist(_dist){}
};
Edge ed[maxm];int he[maxn],ne[maxm],etop=1;
void insert(int u,int v,ll w){ed[etop]=Edge(u,v,w);ne[etop]=he[u];he[u]=etop++;}ll d[maxn][30];
bool vis[maxn][30];
struct node{int to,level;ll cost;friend bool operator < (node a,node b){return a.cost>b.cost;}
};
priority_queue<node>q;void dijkstra(int s){memset(vis,0,sizeof(vis));memset(d,0x3f,sizeof(d));d[s][0]=0;q.push(node{s,0,0});while(!q.empty()){int now = q.top().to,p=q.top().level;        //cout<<d[now][p]<<" "<<q.size()<<endl;q.pop();if(!vis[now][p]){vis[now][p] = true;for(int i = he[now]; i; i = ne[i]){Edge& e = ed[i];if(!vis[e.to][p]&&d[e.to][p]>d[now][p]+e.dist){d[e.to][p]=d[now][p]+e.dist;q.push(node{e.to,p,d[e.to][p]});}if(p<k&&!vis[e.to][p+1]&&d[e.to][p+1]>d[now][p]){d[e.to][p+1]=d[now][p];q.push(node{e.to,p+1,d[e.to][p+1]});}}}}
}