入门级别的分层图最短路

前言

先介绍一下分层图最短路。

分层图最短路是指在可以进行分层图的图上解决最短路问题。
一般模型是：
在图上，有k次机会可以直接通过一条边，问起点与终点之间的最短路径。

题目描述

Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务，设这些城市分别标记为00到n-1n−1，一共有mm种航线，每种航线连接两个城市，并且航线有一定的价格。

Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多kk种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？

输入输出格式

输入格式

数据的第一行有三个整数，n,m,k，分别表示城市数，航线数和免费乘坐次数。

第二行有两个整数，s,t，分别表示他们出行的起点城市编号和终点城市编号。

接下来有m行，每行三个整数，a,b,c，表示存在一种航线，能从城市a到达城市b，或从城市b到达城市a，价格为c。

输出格式

只有一行，包含一个整数，为最少花费。

输入输出样例

输入样例#1：

输出样例#1：

解题思路

这就是分层图最短路的模板
但为什么是省选/NOI-呢

我们用DP的思想来看
设dis[i][j]表示起点到i点在j层的最短路

如何分层？
理解性记忆。
例如本题最多有十层，第k层表示免费了k次的最短路

如何跑最短路？
洛谷卡SPFA，BZOJ不卡SPFA，但是都要注意把空间开大10倍，不然是过不去的（5次TLE的惨痛经验）
在跑 Dijkstra 的时候，我们用了一个pair来存当前到达的点和已走过的路径；这次我们需要多维护一个东西：当前的层数。

struct Node {
    int id; // 当前到达的点
    int weight; // 已走过的路径
    int now; // 当前的层数

    Node() {
        id = weight = now = 0;
    }

    // 重载运算符，用于优先队列
    bool operator < (const Node &that) const {
        return weight > that.weight;
    }
};

在更新dis的时候，我们需要对这一层的点和下一层的点分别进行更新

if (!vis[to][Floor] && dis[to][Floor] > dis[now][Floor] + edge[e].weight) {
    dis[to][Floor] = dis[now][Floor] + edge[e].weight;
    q.push(NewNode(to, dis[to][Floor], Floor));
}

if (!vis[to][Floor] && Floor + 1  dis[now][Floor]) {
    dis[to][Floor + 1] = dis[now][Floor];
    q.push(NewNode(to, dis[to][Floor + 1], Floor + 1));
}

代码实现

/* -- Basic Headers -- */
#include 
#include 
#include 
#include 
#include 
#include 

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

namespace FastIO {
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
    const int MAXN = 100000 + 10;
    const int MAXM = 500000 + 10;
    const int MAXK = 10 + 5;

    struct Node {
        int id, weight, now;
        Node() {
            id = weight = now = 0;
        }
        bool operator < (const Node &that) const {
            return weight > that.weight;
        }
    } head[MAXN];

    struct Edge {
        int now, next, weight;
    } edge[MAXM];

    int n, m, k, s, t, K, cnt, dis[MAXN][MAXK];
    bool vis[MAXN][MAXK];

    inline void addEdge(int prev, int next, int weight) {
        edge[++cnt].now = next;
        edge[cnt].weight = weight;
        edge[cnt].next = head[prev].id;
        head[prev].id = cnt;
    }

    Node NewNode(int id, int weight, int now) {
        Node tmp;
        tmp.id = id;
        tmp.weight = weight;
        tmp.now = now;
        return tmp;
    }

    void SPFA() {
        memset(dis, 0x7f, sizeof(dis));
        std::priority_queue q;
        For (i, 0, K) dis[s][i] = 0;
        q.push(NewNode(s, 0, 0));
        while (!q.empty()) {
            Node NowNode = q.top();
            q.pop();
            int Floor = NowNode.now;
            int now = NowNode.id;
            if (vis[now][Floor]) continue;
            vis[now][Floor] = true;
            for (int e = head[now].id; e; e = edge[e].next) {
                int to = edge[e].now;
                if (!vis[to][Floor] && dis[to][Floor] > dis[now][Floor] + edge[e].weight) {
                    dis[to][Floor] = dis[now][Floor] + edge[e].weight;
                    q.push(NewNode(to, dis[to][Floor], Floor));
                }
                if (!vis[to][Floor] && Floor + 1  dis[now][Floor]) {
                    dis[to][Floor + 1] = dis[now][Floor];
                    q.push(NewNode(to, dis[to][Floor + 1], Floor + 1));
                }
            }
        }
    }
}

signed main() {
    using namespace Solution;
    using FastIO::getint;
    n = getint();
    m = getint();
    k = getint();
    s = getint();
    t = getint();
    K = k;
    For (i, 1, m) {
        int prev = getint();
        int next = getint();
        int weight = getint();
        addEdge(prev, next, weight);
        addEdge(next, prev, weight);
    }
    SPFA();
    int ans = 2147482333;
    for (int i = 0; i <= k; ++i) {
        ans = std::min(ans, dis[t][i]);
    }
    FastIO::putint(ans, '\n');
    return 0;
}

飞行路线