D、小雨坐地铁

思路：

分层建图，求单源最短路。
想到求最短路，不带负权边，很容易想到迪杰斯特拉算法，但是这并不是给你n个点m条边让你建好图再问你最短路，这里最难想到的就是怎么建图化为求最短路的一般情况。
将每条地铁线看作一层图，因为每层之间可能公用了一些节点，所以我们对每个车站建立一个超级源点放在第m+1层， 车站到超级源点的花费是0, 超级源点往车站的花费是上地铁的花费，因为从源点到车站表示第一次上地铁，而从车站到超级源点表示他要转地铁（转地铁的搭配是车站到超级源点再到其它层的该车站）。
每一层假设有n个结点（有强迫症你可以这一层有几个就放几个，但是在连这一层的该车站到超级源点的边时，超级源点的取值又不知道，反正又不浪费多少空间），第i层第j个车站的编号就是(i-1)*n+a[j]。
因为取了m+1层，每层n个单位，所以最多有有(m+1) * n个不重复的编号.

注意：到起点最短的结点集合是A，集合A的邻居放进集合B。集合B里可能有两个一样的邻居，但是有一个邻居是要去掉的。必须要存放进去的邻居和它连起来的最短路，比如集合B里有两个一样的邻居u=2,dis=5和u=2,dis=4，这里邻居u=2,dis=5是要去掉的，所以要用优先队列存集合，并重载'<'，使距离起点最小的邻居出队，再标记已经出队的邻居（找到最短路了），这样在遇到距离大一点的邻居u=2,dis=5时判断已经出队然后就可以抛弃了。

Code：

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int maxn=501005;
int head[maxn],Next[maxn<<1],to[maxn<<1],tot,val[maxn<<1];
void add(int x,int y,int c) {
    to[++tot]=y;
    val[tot]=c;
    Next[tot]=head[x];
    head[x]=tot;
}
struct node{
    int v,dis;
    bool operator<(const node&a) const{
        return dis>a.dis;
    }
};
int n,m,dis[maxn];
bool done[maxn];//done[i]=true表示到结点i的最短路径已经找到
void dijkstra(int s) {
   fill(dis, dis + maxn, 0x3f3f3f3f);
    dis[s]=0;    //起点到自己的距离是0
    priority_queue<node>q;//优先队列，存结点的信息
    q.push(node{s,0});//起点进栈
    while(!q.empty()) {
        node u=q.top();
        q.pop();
        if(done[u.v]) continue;//丢弃已经找到最短路径的结点，即集合A中的结点
        done[u.v]=true;
        for(int i=head[u.v];i;i=Next[i]) {
            int y=to[i];
            if(done[y])    continue;
            if(dis[y]>val[i]+u.dis) {
                dis[y]=val[i]+u.dis;
                q.push(node{y,dis[y]});
            }
        }
    }
}
int s,t,num,x,last,a,b;
int main() {
    js;
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;++i) {
        cin>>a>>b>>num;
        for(int j=1;j<=num;++j) {
            cin>>x;
            if(j!=1) {
                add(i*n+x,i*n+last,b);
                add(i*n+last,i*n+x,b);
            }
            add(i*n+x,n*m+x,0);
            add(n*m+x,i*n+x,a);
            last=x;
        }
    }
    dijkstra(n*m+s);
    if(dis[n*m+t]==0x3f3f3f3f) cout<<"-1\n";
    else cout<<dis[n*m+t]<<endl;
}