题目

题目描述：
小雨所在的城市一共有 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 号线的每一个车站的编号，单调递增。

输出描述：
共一行，一个数表示最小花费，若不能到达输出 -1 。

解析

分层图最短路径问题（现学）+ Dijkstra
个人觉得题目挺难的。。也是第一次写，煎熬的写（看+问）了好几个小时。真的是辛苦细心教我的大佬了。
首先来讲一下分层图最短路径：
  • 简单来说就是将图分层：每一层放一组自己要的东西，然后不同组之间额外用一层连接起来（称作超级源点层），根据需要，超级源点可以和其他节点之间无权值。
转载自网上大佬的图片。

然后就是Dijkstra：
  • 我们从某一点作为起点向外拓展，每次选取最小边进行操作（为了省时间和方便可以用优先队列），并用一个数组（mp数组）保存到达每个节点的最小值。

这两个概念都简单介绍过之后：
  1. 先初始化我们的数组，这道题根据我刚刚说的，操作都好说，但是建立图形难。（我们以下用n表示地铁站数，用m表示地铁线数）
  2. 我们可以用一个链式表来模拟一个三维结构（vector<Node> subway）：数组每n个位置为一组，每个位置可以链接节点，然后有i层。加上超级源点层数组长度就是n*(m+1)。
  3. 根据以上，我们就能知道，第i层的第k个节点就是i * n + k。我们便以此来索引位置。
  4. 下面就是赋值了，我们只要每一层都将c个数顺序连起来就行了，正反都要连，权值依照输入。（这里要注意地铁换线：进入超级源点层。进地铁花钱，出地铁不花钱）
  5. 初始化完了我们就再建立一个地图（mp数组）来进行Dijkstra就行了。
  6. 详情看代码~

代码 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define js ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MAX = 1e6 + 7;
//代码预处理
struct Node {
    ll to, cost;//抵达站的坐标，花费的价格
    int operator < (const Node& b) const {
        return cost > b.cost;
    }//优先队列，花费小优先。
};
vector<Node> subway[MAX];
ll n, m, s, t;//表示车站个数，地铁线数，起点站和终点站
ll mp[MAX];//作为地图，记录每个车站的最短路径

template<class T>inline void read(T& res);//整型快读函数
void dijkstra();//最短路径

int main() {
    js;
    read(n); read(m); read(s); read(t);
    for (ll i = 0; i < m; i++) {
        ll a, b, c; read(a); read(b); read(c);
        //坐i号线的价格，i号线每坐一站多花的价格，i号线车站个数
        ll last = 0;
        for (ll j = 0; j < c; j++) {
            ll u; read(u);//i号线有u号车站
            if (j) {
                subway[i * n + u].push_back({ i * n + last, b });
                subway[i * n + last].push_back({ i * n + u, b });
            }
            //与同一条线的上一个节点连起来
            subway[i * n + u].push_back({ m * n + u, 0 });
            subway[m * n + u].push_back({ i * n + u, a });
            //进出超级源点（进要花钱，出不花钱）
            last = u;
        }
    }
    dijkstra();
    if (mp[m * n + t] == INF) printf("-1\n");
    else printf("%lld\n", mp[m * n + t]);
    return 0;
}

template<class T>inline void read(T& res) {
    char c; T flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
void dijkstra() {
    memset(mp, INF, sizeof(mp));
    //fill(mp, mp + MAX, INF);
    mp[n * m + s] = 0;
    priority_queue<Node> que;
    que.push({ n * m + s, mp[n * m + s] });
    while (!que.empty()) {
        Node top = que.top(); que.pop();
        if (top.cost > mp[top.to]) continue;
        //如果到该节点花的钱比以前记录的还多，就直接跳过
        for (auto it : subway[top.to])
            if (mp[it.to] > top.cost + it.cost) {
                mp[it.to] = top.cost + it.cost;
                que.push({ it.to, mp[it.to] });
            }
        //如果花的钱更少了就替换上去
    }
}