NC26257小雨坐地铁

最短路分层图

在最短路中由于各种条件的限制会导致建图的时候会建成分层图

分层图中将限制条件给消除，变成普通的单元最短路问题。

链接：https://ac.nowcoder.com/acm/problem/26257
来源：牛客网

题目描述

小雨所在的城市一共有 mmm 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 nnn 个车站，编号为 1∼n1 sim n1∼n 。其中坐 i 号线需要花费 aia_iai 的价格，每坐一站就需要多花费 bib_ibi 的价格。i 号线有 cic_ici 个车站，而且这 cic_ici 个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 sss 个车站坐地铁到第 ttt 个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 -1 。（地铁是双向的，所以 sss 可能大于 ttt）

输入描述:

第一行输入四个正整数 n,m,s,tn,m,s,tn,m,s,t，分别表示车站个数，地铁线数，起点站和终点站。
第二行到第 m+1m + 1m+1 行，每行前三个数为 ai,bi,cia_i,b_i,c_iai,bi,ci，分别表示坐 i 号线的价格，i 号线每坐一站多花的价格，i 号线车站个数。接下来 cic_ici 个数，表示 i 号线的每一个车站的编号，单调递增。

输出描述:

共一行，一个数表示最小花费，若不能到达输出 -1 。

思路：

建立一个如图的分层图，第一层图代表的是第一条线上的各个站点，以此类推。

第m+1层，也即虚点的一层。将每条线上的每个站点都与对应的虚点的站点相连，虚点->地铁线的边权是a，地铁线->虚点的边权为0，然后建立分层图。

需要注意的是最后求解距离时要求的是虚点一层的起点->终点。
求1—>4 ，
从虚点1出发，到第一条线1，花费为2，
从1再到3 花费为2
从第一条线3再到虚点3 花费为0
虚点3到第二条线3 花费为2
从第二条线3到4 花费为1
总花费为7
此类问题注意初始化问题。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl 'n'
#define mem(a,b) memset(a,b,sizeof(a))
#define debug(case,x); cout<<case<<"  : "<<x<<endl;
#define open freopen("ii.txt","r",stdin)
#define close freopen("oo.txt","w",stdout)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> PII;
const int maxn = 1e6 + 10;
int n,m,s,t;

struct edge{
    int next,to,val;
}edge[maxn];
int head[maxn],tot=0;

void add(int u,int v,int val){
    edge[++tot].to=v;
    edge[tot].next=head[u];
    edge[tot].val=val;
    head[u]=tot;
}
int dis[maxn],vis[maxn];
priority_queue<pii,vector<pii>,greater<pii> >qp;
void dij(int src){
    while(!qp.empty())qp.pop();
    dis[src]=0;
    qp.push({0,src});
    while(!qp.empty()){
        pii tt=qp.top();qp.pop();
        int u=tt.second;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].next){
            if(dis[edge[i].to]>dis[u]+edge[i].val){
                dis[edge[i].to]=dis[u]+edge[i].val;
                qp.push({dis[edge[i].to],edge[i].to});
            }
        }
    }

}

int main(){
//    open;close;
    cin>>n>>m>>s>>t;
    for(int i=0;i<=n*(m+1);++i)dis[i]=INF,head[i]=-1;
    for(int p=1;p<=m;++p){
        int a,b,c,pre;cin>>a>>b>>c;
        for(int i=1;i<=c;++i){
            int x;cin>>x;
            add((p-1)*n+x,n*m+x,0);
            add(n*m+x,(p-1)*n+x,a);
            if(i!=1){
                add((p-1)*n+pre,(p-1)*n+x,b);
                add((p-1)*n+x,(p-1)*n+pre,b);
            }
            pre=x;
        }
    }
    dij(m*n+s);
    if(dis[m*n+t]==INF)cout<<-1<<endl;
    else cout<<dis[m*n+t]<<endl;

}

参考博客