小雨坐地铁--[最短路分层建图+虚点]

也是第一次接触这种分层建图的最短路
思路：由题目我们可以知道某些站点是可以连接好几条地铁线路的，那么对于每条地铁线路我们可以把他当成一幅图来算。当然图是个无向图，所以要加两次边。

add(i*n+x,i*n+pre,b); //乘i的话就是说把他建在第i层，这个pre是记录上一个点的位置。 add(i*n+pre,i*n+x,b); 

处理换乘时的操作
利用到我们刚刚所说的虚点

add(x,i*n+x,a); //从虚点到地铁线上需要花费，花费坐这条线的价格 //也就是题中（坐i号线需要花费a[i]的价格）  add(i*n+x,x,0); //从地铁线上到虚点花费为0 

根据题目中样例建成的图就是（图来源于大佬博客）https://blog.nowcoder.net/n/149da7cef2d8451d8ff1e319ebc6e663

接下来的过程就跟最短路模板题一样了
代码：

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn  1000010
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;
struct wazxy{
    int to,w,next;
}edge[maxn];
struct node{
    int n,dis;
    node(int a,int b){n=a,dis=b;}
    bool operator <(const node & a)const
    {return dis>a.dis;}
};
int dis[maxn];
int head[maxn];
int cnt=0,n,m,s,t;
bool visited[maxn];
void init(){
    memset(head,-1,sizeof(head));
    memset(visited,false,sizeof(visited));
    memset(dis,MaxN,sizeof(dis));
}
void add(int u,int v,int w){
    edge[cnt].w=w;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void dij(int x){
    dis[x]=0;
    priority_queue<node> q;
    q.push(node(x,0));
    while(!q.empty()){
        node temp=q.top();
        q.pop();
        if(visited[temp.n]) continue;
        visited[temp.n]=true;
        for(int i=head[temp.n];~i;i=edge[i].next){
            int v=edge[i].to;
            int w=edge[i].w;
            if(visited[v]) continue;
            if(dis[v]>temp.dis+w){
                dis[v]=temp.dis+w;
                q.push(node(v,dis[v]));
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s>>t;
    init();
    for(int i=1;i<=m;i++){
        int a,b,c,x;
        scanf("%d%d%d",&a,&b,&c);
        int pre=-1;
        while(c--){
            cin>>x;
            if(pre!=-1){
                add(i*n+x,i*n+pre,b);  //乘i的话就是说把他建在第i层
                add(i*n+pre,i*n+x,b);
            }
            add(x,i*n+x,a);
            add(i*n+x,x,0);
            pre=x;
        }
    }
    dij(s);
    if(dis[t]==MaxN) cout<<"-1"<<endl;
    else cout<<dis[t]<<endl;
    return 0;
}