题目描述

小雨所在的城市一共有 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 。

题解

分层图+最短路
我们可以把每一条地铁线看作一层，对于层与层之间我们建立虚点，把不同的层之间联系起来，然后再跑最短路就OK了
那我们怎么进行分层建图呢？对于第i条线路的边，我们对其标号为i*n+x，即第一层的边是从n到2n,第二层的边是从2n到3n...以此类推。我们把所有虚点建到1到n之间，如下图：
图片说明
所以我们只需要把图建好然后跑最短路就好啦。

代码

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=1e6+100;
int n,m,S,T;
int dis[N];
int head[N];
struct node{
    int to,net,w;
}s[N*3];
int tot=0;
void add(int u,int v,int w){
    s[++tot]={v,head[u],w};
    head[u]=tot;
}
void dij(){
    priority_queue<pii > Q;
    Q.push({0,S});
    dis[S]=0;
    while(!Q.empty()){
        pii now=Q.top();
        Q.pop();
        for(int i=head[now.se];~i;i=s[i].net){
            int z=s[i].to;
            if(dis[z]>dis[now.se]+s[i].w){
                dis[z]=dis[now.se]+s[i].w;
                Q.push({-dis[z],z});
            }
        }
    }
    if(dis[T]<0x3f3f3f3f)cout<<dis[T]<<'\n';
    else cout<<-1<<'\n';
}
////////////////////////////////////////////////////////////////////////
int main(){
    n=gn(),m=gn(),S=gn(),T=gn();
    for(int i=0;i<=(m+1)*n;++i){
        head[i]=-1;
        dis[i]=0x3f3f3f3f;
    }
    repi(i,1,m){
        int a=gn(),b=gn(),c=gn();
        int last=-1;
        repi(j,1,c){
            int x=gn();
            if(j>1){
                add(i*n+x,i*n+last,b);
                add(i*n+last,i*n+x,b);
            }
            add(x,i*n+x,a);
            add(i*n+x,x,0);
            last=x;
        }
    }
    dij();
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/