分层图+最短路

ps：刚刚开始看这个题目的时候，看完一遍不理解，再看一遍还是不理解，于是冷静一波~发现这个题目真的很复杂！！！
题目是求最短路，最短路可以参考我的另外一篇博客快速理解最短路径算法

对于这个题目而言，我们需要去做出一个分层图出来，因为地铁线之间有交叉，所以在存储完地铁线之后，我们需要对建立一个超级源点，并且规定，从地铁站到超级源点需要不需要花费，而从超级源点到地铁站需要花费，这就相当于一个中转站一样，我们通过中转站去下一个地铁当然需要花费，超级源点相当于一条虚拟的地铁站，该线上有所有的地铁站虚点。

分层图就是一层一层的，这样我们就可以知道当前节点的位置坐标，就相当于一个二维数组，不同的是这个二维数组存在三维空间中

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
int cnt, vis[maxn], dis[maxn], head[maxn], a[maxn], b[maxn];
struct node //结构体存储边的信息，起点，终点，边权，下一个节点
{
    int  v, w, next;
} e[maxn];

void add(int u, int v, int w) //链式前向星存图，每次加边都放在头结点的后面，降低时间复杂度
{
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

queue<int> q;
void spfa(int x)
{
    memset(dis, inf, sizeof(dis)); //初始化
    memset(vis, 0, sizeof(vis));
    vis[x] = 1; //标记该节点已经使用
    dis[x] = 0; //该节点到自己的距离为0
    q.push(x);    //放入队列
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;                                 //出队
        for (int i = head[u]; ~i; i = e[i].next) //遍历该节点所有的邻接点
        {
            int v = e[i].v;                  //后继节点
            if (dis[v] > dis[u] + e[i].w) //松弛操作
            {
                dis[v] = dis[u] + e[i].w;
                if (!vis[v]) //判断该节点是否遍历过
                {
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
int main()
{
    int n, m, s, t, sum, x, last;
    cnt = 0;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &a[i], &b[i], &sum);
        for (int j = 1; j <= sum; ++j)
        {
            scanf("%d", &x);
            if (j != 1) //第一个地铁站因为前面为空，所以直接和超级源点相连接，其余节点不仅要和超级源点链接，还要和上一个节点连接
            {
                add((i - 1) * n + x, (i - 1) * n + last, b[i]); //加边操作从当前节点到上一个节点需要花费b[i]
                add((i - 1) * n + last, (i - 1) * n + x, b[i]); //由于是无向图，所有从上一个节点到当前节点需要的花费也是b[i]
            }
            add((i - 1) * n + x, n * m + x, 0);       //地铁站到超级源点不需要花费
            add(n * m + x, (i - 1) * n + x, a[i]); //超级源点到地铁站需要花费a
            last = x;                               //储存上一个地铁站
        }
    }
    spfa(n * m + s); //开始跑spfa
    if (dis[n * m + t] == inf)
        printf("-1\n");
    else
        printf("%d\n", dis[n * m + t]);
    return 0;
}