小雨坐地铁

题目描述
小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 n个车站，编号为 1∼n 。其中坐 i 号线需要花费 ai的价格，每坐一站就需要多花费 bi 的价格。i 号线有 ci 个车站，而且这 ci 个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 s 个车站坐地铁到第 t个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 -1 。（地铁是双向的，所以 s可能大于 t）
输入描述:
第一行输入四个正整数 n,m,s,t分别表示车站个数，地铁线数，起点站和终点站。
第二行到第 m+1 行，每行前三个数为 ai,bi,ci，分别表示坐 i 号线的价格，i 号线每坐一站多花的价格，i 号线车站个数。接下来 ci个数，表示 i 号线的每一个车站的编号，单调递增。

思路：
每条地铁线路可以看做一层图，一层一层图之间正常建边即可。每层之间可能是相连的，对应每个车站设立一个虚点。虚点连向车站的花费是上地铁的钱（或转地铁的钱）。而车站连接虚点花费为0，建立虚点时，不用根据层与层间连边，这样每层都要连，就要m m n条边，而设立虚点只要n m 2。
代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e5 + 5;
const int INF = 0x3f3f3f3f;
int n,m,s,t,ss;
struct edge{int v,w;edge(int x,int y){v=x,w=y;}};
vector<edge>v[N];
int vis[N],dis[N];
struct node{
    int num,dis;
    node(int x,int y){num=x,dis=y;};
    friend bool operator >(const node &a,const node &b){return a.dis>b.dis;}
};
void add(int x,int y,int z){
    v[x].push_back(edge(y,z));
}
void Dig(int s,int t){
    memset(dis,INF,sizeof(dis));
    dis[s]=0;
    priority_queue<node,vector<node> ,greater<node> >q;
    q.push(node(s,0));
    while(!q.empty()){
        node now=q.top();
        q.pop();
        int u=now.num;
        if(vis[u])continue;
        vis[u]=1;
        for(int i=0;i<v[u].size();i++){
            edge next=v[u][i];
            if(vis[next.v])continue;
            if(dis[u]+next.w<dis[next.v]){
                dis[next.v]=dis[u]+next.w;
                q.push(node(next.v,dis[next.v]));
            }
        }
        if(dis[t]!=INF){cout<<dis[t];return;}
    }
    //for(int i=1;i<=n;i++)cout<<dis[i]<<' ';
    cout<<-1;
}
void solve(){
    //memset(v,0,sizeof(v));
    //memset(vis,0,sizeof(vis));
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int a,b,c;cin>>a>>b>>c;
        int x=-1,y=-1;
        for(int j=0;j<c;j++){
            cin>>y;y--;
            if(x!=-1){
                add(i*1000+x,i*1000+y,b),add(i*1000+y,i*1000+x,b);
            }
            add(i*1000+y,y,0),add(y,1000*i+y,a);
            x=y;
        }
    }
    s--,t--;
    Dig(s,t);
}
int main(){
    solve();
}