D、小雨坐地铁

分层建图，求单源最短路，不带负权边。
如果单看最短路，不带负权边，很容易想到迪杰斯特拉算法，那么还有一个主要问题就是这个图怎么建立了。
我们知道对于一条地铁线，存在最大N个结点，如果不够也没关系，我们对这一条地铁线上的点进行建边，假设第一条地铁线在第一层，花费为地铁一站的花费，那么第二条地铁线在第二层，这层地铁线可能也用到了第一层某个站点，我们就要对应在M+1层开一个超级源点，从站点去超级源点假设花费为0，那么从超级源点去往某一条地铁线中的点就是转线或者上地铁了，花费记作上地铁的花费。
那么我们的迪杰斯特拉算法就变成了，从超级源点中的起点，去往超级源点中的终点。存在的最短路，直接求解即可，判断是否小于等于初始化的INF，直接输出答案就OK了。

vector相比于前向星码量小，适合我这种懒人，卡vector的 坑爹 良心出题人想让我们多用用更好的方案

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43533955

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 5e5+3e3; //节点数
const int M = 5e5 + 7; //路径数
const ll INF = 1e18;
ll d1[N];
struct Node {
    int v;
    ll cost;
    bool operator < (Node b)const {
        return cost > b.cost;
    }
};
vector<Node> e[N];
int n, m, st, ed;

void dijkstra(int s, ll d[]) {
    priority_queue<Node>  pq;
    fill(d, d + N, INF);
    d[m * n + s] = 0;
    pq.push(Node{ m * n + s,0 });
    while (!pq.empty()) {
        Node    x = pq.top();
        pq.pop();
        if (d[x.v] < x.cost)    continue; //原先这个节点花费更少 跳过
        for (auto it : e[x.v]) {
            if (d[it.v] > x.cost + it.cost) {
                d[it.v] = x.cost + it.cost;
                pq.push(Node{ it.v,d[it.v] });
            }
        }
    }
}

int main() {
    n = read(), m = read(); st = read(), ed = read();
    for (int i = 0; i < m; ++i) {
        int a = read(), b = read(), c = read(), x = read();
        e[i * n + x].push_back(Node{ m * n + x, 0 });
        e[m * n + x].push_back(Node{ i * n + x, a });
        while (--c) {
            int y = read();
            e[i * n + x].push_back(Node{ i * n + y, b });
            e[i * n + y].push_back(Node{ i * n + x, b });
            e[i * n + y].push_back(Node{ m * n + y, 0 });
            e[m * n + y].push_back(Node{ i * n + y, a });
            x = y;
        }
    }
    dijkstra(st, d1);
    if (d1[m * n + ed] == INF)  puts("-1");
    else    printf("%lld\n", d1[m * n + ed]);
    return 0;
}