题解：P12332 [蓝桥杯 2023 省 Java B] 魔法阵

· · 题解

题目传送门

观察到 k 极小，所以你直接考虑对原图建分层图。考虑再分层图上的两种转移（设层数 i\in [0,k]）：

  1. 这条边没选，需要满足 i=0 或 i=k，那么直接在第 i 层图转移。转移时边权按原边权算。
  2. 这条边选了，需要满足 i<k，那么从第 i 层图转移到第 i+1 层图，转移时边权按 0 算。

答案即为 \min(f_{n-1,0},f_{n-1,k})。

实际上只需要在松弛更新的时候考虑这两种转移即可，根本不需要把分层图建出来。直接硬跑 dij 或 已死算法spfa 都能过。

#include <bits/stdc++.h>
using namespace std;
#define il inline
#define mkp make_pair
#define pi pair<int, int>
typedef long long ll;
const int N = 1e3 + 10, K = 11;
int f[N][K], inf = 1e9, n, m, k;
queue<pi> q;
vector<pi> g[N];
bool inque[N][K];
il void spfa(int s)
{
    for(int i = 0;i < n;++i)
        for(int j = 0;j <= k;++j)
            f[i][j] = inf;
    f[s][0] = 0;
    inque[s][0] = 1;
    q.push(mkp(s, 0));
    while(q.size())
    {
        pi cur = q.front();
        q.pop();
        int u = cur.first, j = cur.second;
        inque[u][j] = 0;
        for(auto vv : g[u])
        {
            int v = vv.first, w = vv.second;
            if((j == 0 || j == k) && f[v][j] > f[u][j] + w)
            {
                f[v][j] = f[u][j] + w;
                if(!inque[v][j])
                {
                    q.push(mkp(v, j));
                    inque[v][j] = 1;
                }
            }
            if(j < k && f[v][j + 1] > f[u][j])
            {
                f[v][j + 1] = f[u][j];
                if(!inque[v][j + 1])
                {
                    q.push(mkp(v, j + 1));
                    inque[v][j + 1] = 1;
                }
            }
        }
    }
}
int main()
{
    cin >> n >> k >> m;
    while(m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back(mkp(v, w));
        g[v].push_back(mkp(u, w));
    }
    spfa(0);
    cout << min(f[n - 1][0], f[n - 1][k]);
    return 0;
}