题意

告诉你车站数n，地铁线路数m，起点s，终点t，然后m行描述每一条地铁的上车价格a，每坐一站价格b，车站数c，以及c个车站号，求最小花费。

题解

显然，是一个很裸的最短路。但是直接以站点为节点，地铁线路作为边是不能简单的用Dij过的，毕竟贪心算法，直接这么莽会wa的（我还真试过，wa了，自己也找出了错误的例子）。

于是我们可以从建图上做一点手脚，让他变成一个常规的最短路问题。此时，变得运用上分层建图思想了。

分层建图

在这边我们以样例为例，使用分层建图思想建立一遍图形。

我们将站点和车辆分开，上车需要花费a元，下车不要钱，图中没有箭头的表示他是一个双项链接，橙色便是车站构成的虚点，绿色的均为地铁的描述。

struct ST {
    int n; // 去哪个站
    int w; // 一站的钱

    bool operator< (const ST &other) const {
        return w > other.w;
    }
};

vector<ST> g[1000010]; // 开得大一点

int main()
{
    int n,m,s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int a,b,c;
    int ci[1010];
    for (int i = 1;i <= m;i ++) {
        scanf("%d%d%d%d",&a,&b,&c,ci);
        for (int j = 0;j < c;j ++) {
            if (j != 0) {
                scanf("%d",ci + j);
                g[ci[j - 1] + n * i].push_back({ci[j] + n * i,b}); // 描述地铁线路，其中+ n * i则是为了不与别的地铁线路和站点的虚点所重复
                g[ci[j] + n * i].push_back({ci[j - 1] + n * i,b}); // 建立双向图
            }

            g[ci[j]].push_back({ci[j] + n * i,a}); // 链接站点虚点与地铁站点，从站点到地铁上车要收a元
            g[ci[j] + n * i].push_back({ci[j],0}); // 下车不要钱
        }
    }
    return 0;
}

这样建立完图之后，就可以快乐地套Dijkstra模版啦。

int dis[1000010];
int vis[1000010] = {0};

void dij(int s) {
    mem(dis,-1);

    priority_queue<ST> q;
    q.push({s,dis[s] = 0});

    ST current;
    int k;
    while (!q.empty()) {
        current = q.top();
        q.pop();
        if (vis[current.n]) continue;
        vis[current.n] = 1;

        for (auto to : g[current.n]) {
            k = dis[current.n] + to.w;
            if (dis[to.n] == -1 || dis[to.n] > k) {
                q.push({to.n,dis[to.n] = k});
            }
        }
    }
}

完整代码

//
//  header_useful.h
//  c++_acm
//
//  Created by VoidJack_Lee on 2019/7/23.
//  Copyright © 2019 VoidJack_Lee. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <vector>
#include <list>
#include <set>
#include <utility> // pair
#include <map>
#include <iostream>
#include <sstream>
#include <algorithm> // sort
#include <string>
#include <stack>
#include <queue>
#include <fstream>
#include <bitset>

using namespace std;

#define ll long long
#define uchar unsigned char
#define ushort unsigned short
#define uint unsigned int
#define ulong unsigned long
#define ull unsigned long long

#define INT_INF 0x7fffffff

#define pi acos(-1)

#define mx(a,b) (a) > (b) ? (a) : (b)
#define mn(a,b) (a) < (b) ? (a) : (b)
#define mem(a,b) memset(a,b,sizeof(a))
#define fre(a) freopen(a,"r",stdin)

#define cio ios::sync_with_stdio(false); // Do not use it with "scanf" and other c input!

#define itn int
#define nit int
#define inr int
#define mian main
#define ednl endl
#define fro for
#define fir for
#define reutrn return
#define retunr return
#define reutnr return


/* header_useful_h */

int dis[1000010];

int vis[1000010] = {0};

struct ST {
    int n; // 去哪个站
    int w; // 一站的钱

    bool operator< (const ST &other) const {
        return w > other.w;
    }
};
vector<ST> g[1000010];

void dij(int s) {
    mem(dis,-1);

    priority_queue<ST> q;
    q.push({s,dis[s] = 0});

    ST current;
    int k;
    while (!q.empty()) {
        current = q.top();
        q.pop();
        if (vis[current.n]) continue;
        vis[current.n] = 1;

        for (auto to : g[current.n]) {
            k = dis[current.n] + to.w;
            if (dis[to.n] == -1 || dis[to.n] > k) {
                q.push({to.n,dis[to.n] = k});
            }
        }
    }
}

int main()
{
    int n,m,s,t;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    int a,b,c;
    int ci[1010];
    for (int i = 1;i <= m;i ++) {
        scanf("%d%d%d%d",&a,&b,&c,ci);
        for (int j = 0;j < c;j ++) {
            if (j != 0) {
                scanf("%d",ci + j);
                g[ci[j - 1] + n * i].push_back({ci[j] + n * i,b});
                g[ci[j] + n * i].push_back({ci[j - 1] + n * i,b});
            }

            g[ci[j]].push_back({ci[j] + n * i,a});
            g[ci[j] + n * i].push_back({ci[j],0});
        }
    }
    dij(s);
    printf("%d\n",dis[t]);
//
//
//    for (int i = 1;i <= n;i ++) printf("%d ",vis[i]);
//    printf("\n");
//
//
//    for (int i = 1;i <= n;i ++) printf("%d ",dis[i]);
//    printf("\n");
//
    return 0;
}