• 前言
• 题目大意
• 思路
• 代码
• 总结

前言

分层图的难点在于如何建模，建模之后的做法当成一个图做就行了。

题目大意

有 $n$ 个结点，$m$ 条边。从 $s$ 出发，$t$ 结束。每条边有边权。在走的过程中可以使用 $k$ 次不消耗边权通过一条边。求最短路。

对于 $100\%$ 的数据，$2 \le n \le 10^4$，$1 \le m \le 5\times 10^4$，$0 \le k \le 10$，$0\le s,t,a,b\le n$，$a\ne b$，$0\le c\le 10^3$。

思路

如果没有“免费”的限制，直接最短路跑一遍就行了。所以把重心放到那里。

分层图就是说让一张图“分裂”，变成上上下下的关系。我们可以这么定义：

一共 $k$ 层，编号从 $0$ 到 $k-1$。每一个编号代表还有几次“免费” 可以用。$0$ 层很明显就是原图。之后考虑连接不同层。

假设 $u,v$ 之间有一条边，它们在第 $l$ 层。那么 $u,v+n$ 的位置就有边权为 $0$ 的一条边。由于无向边，$u+n,v$ 也有一条边权为 $0$ 的边。

这样大体思路就出来了。剩下的放到代码里说。

代码

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const ll MAXN=5e6;
const ll MOD=1e9+7;
ll n,m,k,s,t;
ll d[MAXN],ed[MAXN],nxt[MAXN],to[MAXN],w[MAXN],cnt,inq[MAXN];
bool vis[MAXN];
void add_edge(ll u,ll v,ll W){
    nxt[++cnt]=ed[u];
    ed[u]=cnt;
    w[cnt]=W;
    to[cnt]=v;
}
struct node{
    ll v,w;
    bool operator < (const node K)const{
        return K.w<w;
    }
};
void dijkstra(){
    memset(d,0x3f,sizeof(d));
    priority_queue<node>q;
    d[s]=0;
    node A;
    A.v=s;
    A.w=0;
    q.push(A);
    while (!q.empty()){
        node F=q.top();
        q.pop();
        if(inq[F.v]){
            continue;
        }
        //cout<<F.v<<" "<<d[F.v]<<endl;
        inq[F.v]=1;
        for (ll i = ed[F.v]; i ; i=nxt[i]) {
            if(d[F.v]+w[i]<d[to[i]]){
                d[to[i]]=d[F.v]+w[i];
                if(!inq[to[i]]){
                    A.v=to[i];
                    A.w=d[to[i]];
                    q.push(A);
                }
            }
        }
    }
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    scanf("%lld%lld",&s,&t);
    for (int i = 1; i <=m ; ++i) {
        ll u,v,W;
        scanf("%lld%lld%lld",&u,&v,&W);
        add_edge(u,v,W);
        add_edge(v,u,W);
        for (int j = 1; j <=k ; ++j) {
            add_edge(u+(j-1)*n,v+j*n,0);//为了方便，可以画画图理解一下。
            add_edge(v+(j-1)*n,u+j*n,0);
            add_edge(u+j*n,v+j*n,W);//让l层本身联通，我瞎起名叫平行联通，上面的叫上下联通。
            add_edge(v+j*n,u+j*n,W);//同上，无向边。
        }
    }
    for (int i = 1; i <=k ; ++i) {
        add_edge(t+(i-1)*n,t+i*n,0);//防止卡
    }
    dijkstra();//跑一遍所有层构成的大图的最短路
    cout<<d[t+k*n]<<endl;//最后一层的t点位置
    return 0;
}

总结

分层图好像一个水管一样，每一次把能流的插一个水管让它可以留到下一层去。难点在于建模。