【分层图最短路】小雨坐地铁

短命女 2024-03-24 11:36 18阅读 0赞

**分层图  
分层图只是建图时有区别，但跑最短路板子都是一样的，正所谓图论最难的就是建图，只要有合适的建图方法，那么问题就很简单了。**

**分层图是指有很多个平行的图，各个平行的图之间有特殊的连接边。**

**如何更好的理解分层图呢，就想一下我们平时坐的地铁，地铁的某一条线就是一层图，有三条线就相当于有三层平行的图，每层之间通过共有的地铁站连接起来。这就是分层图。**

**用分层图的几种情况：  
1、 有k个不同集合的边，将每个集合内的边建成一张图，再建立第k+1个图，是一个虚层，用这个虚层将这k张图连接起来。每次可以通过虚层转移到另一个集合的图中。如例1.小雨坐地铁。  
2、 有k个机会使得走当前此边不花费代价或花费特殊的代价，可以建立k张相同的该图，每张图之间用有边的点连接起来，其代价是0或是特殊的值。每向下走一层，就代表用了一次机会，使得当前的路花费为0，最多可以走k次。如例2.飞行路线。  
3、 有k个机会逆向行驶，我们可以建k张相同的该图，将每层图之间有边的两个点用的逆向的边连接。每向下走一层，就代表用了一次机会逆向走了一次，最多可以走k次。**

题意：

![b7aa022589aa49289e97fe3e645e4c4e.png][]

**思路：** 这就是建分层图的第一种情况，有k条地铁线路，我们就建k张图，然后再建第k+1张虚层，将各个可以中转线路的点连接起来，并设定从虚层到地铁需要乘该线的代价，从地铁到虚层代价为0，这里的虚层就相当于地铁站，这就实现了地铁的转线。

Code：

#include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    using i64 = long long;
    const int mxn=2e6+10;
    const int mxe=2e6+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    struct ty{
        int to,next,w;
    }edge[mxe<<2];
    struct ty2{
        int x,dis;
        bool operator<(const ty2&a)const{
            return a.dis<dis;
        }
    };
    
    priority_queue<ty2> q;
    int n,m,s,t,x,tot=0;
    int a[mxn],b[mxn],c[mxn],head[mxn],vis[mxn],dis[mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        memset(head,-1,sizeof(head));
    }
    void dij(){
        memset(dis,0x3f,sizeof(dis));
        memset(vis,0,sizeof(vis));
        q.push({s,0});
        dis[s]=0;
        while(!q.empty()){
            ty2 u=q.top();
            q.pop();
            if(vis[u.x]) continue;
            vis[u.x]=1;
            for(int i=head[u.x];~i;i=edge[i].next){
                if(dis[edge[i].to]>dis[u.x]+edge[i].w){
                    dis[edge[i].to]=dis[u.x]+edge[i].w;
                    q.push({edge[i].to,dis[edge[i].to]});
                }
            }
        }
    }
    void solve(){
        cin>>n>>m>>s>>t;
        G_init();
        for(int i=1;i<=m;i++){
            cin>>a[i]>>b[i]>>c[i];
            int last;
            for(int j=1;j<=c[i];j++){
                cin>>x;
                if(j>1){
                    add(i*n+x,i*n+last,b[i]);
                    add(i*n+last,i*n+x,b[i]);
                }
                add(i*n+x,n*n+x,0);
                add(n*n+x,i*n+x,a[i]);
                last=x;
            }
        }
        s=n*n+s;
        t=n*n+t;
        dij();
        if(dis[t]==0x3f3f3f3f) cout<<-1<<'\n';
        else cout<<dis[t]<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[b7aa022589aa49289e97fe3e645e4c4e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/c5632738e08b4fce8873554b113cda2a.png