分层图，建图，最短路

题意：

分析：

首先来看看我当时的思路吧！

我们很容易发现这是个最短路问题，但线路的存在很棘手。雨神说过，图论的难点在于建图！如果成功建图接下来就只是套板子了。那来看看我们如何建图。
我上来也没有思路，后是从实际生活入手的。
想象一下，我们在站点i我们可以坐1,2,3三路高铁，登上1号高铁掏钱a1，登上2号高铁掏钱a2，登上3号高铁掏钱a3
然后我们登上了高铁，假设我们登上了高铁1号线，我们向前开开了一站到达了j站的高铁上,这时我们要在花费b1然后我们从j站的高铁上下来，不用掏钱。

从i站到j站是不是就是这个过程。那我们就模仿这个过程建图就好了嘛。
除了站点之外，我们再建立一个高铁站不就好了，从站点跑上高铁站要是收费，从高铁站跑下站点不要收费。
高铁站线路移动的消耗为b

以样例为例:
5 2 1 4
2 2 3 1 3 5
2 1 4 2 3 4 5

第一条线路：（我们以6，7，8来表示高铁站）

第二条线路：（我们以9，10，11来表示高铁站）

那么合起来就是：

是不是，我们完美的模仿了高铁的功能，并且没有添加其他的功能。
如此我们便解决了这个问题！
在遍历每条线路时，对遍历的点给他建一个高铁站，这条线路遍历完后，对此线路的高铁站再建双向边。
最后再用dijstra算法就完事了。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
struct edge { int to, cost; };
const int max_n = 7e5;
const ll inf = 2e18;
vector<edge> G[max_n];
ll d[max_n];
int n, m;

void dijstra(int s) {
    fill(d + 1, d + 1 + n, inf);
    priority_queue<pll,vector<pll>,greater<pll>> que;
    d[s] = 0;que.push({ d[s],s });
    while (!que.empty()) {
        pll p = que.top();que.pop();
        if (p.first > d[p.second])continue;
        d[p.second] = p.first;
        for (int i = 0;i < G[p.second].size();i++) {
            edge e = G[p.second][i];
            if (d[e.to] > d[p.second] + e.cost) {
                d[e.to] = d[p.second] + e.cost;
                que.push({ d[e.to],e.to });
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    int s, t;
    cin >> n >> m >> s >> t;
    for (int i = 1;i <= m;i++) {
        int a, b, c;cin >> a >> b >> c;
        int st = n + 1;
        for (int j = 1;j <= c;j++) {
            int node;cin >> node;n++;
            G[n].push_back({ node,0 });
            G[node].push_back({ n,a });
        }
        for (int j = st;j < n;j++) {
            G[j].push_back({ j + 1,b });
            G[j + 1].push_back({ j,b });
        }
    }
    dijstra(s);
    if (d[t] == inf)cout << -1 << endl;
    else cout << d[t] << endl;
}

做完，来看题解后才发现这是一种被称为分层图的问题。不说了，去研究研究