acwing-384. 升降梯上

发表于 分类于 阅读次数： Waline： 本文字数： 683 阅读时长 ≈ 2 分钟

考点

  • 最短路
  • 分层图

题解

见思路

思路

设f代表层下标，k代表槽下标，c[k]代表第k个槽的变量，起点等于(第一层, 槽变量等于0的下标) = (1, st)

d[f][k]代表从起点(1, st)到(f, k)的单源最短路，题目要找的是d[n][...]的最小值

很显然这是一个分层图最短路，每一个状态有以下分支：

  1. 选择扳手柄

    1
    2
    3
    4
    5
    6
    for (int i = 1; i <= m; ++i) {
          if (d[f][i] > d[f][k] + abs(i - k)) {
            d[f][i] = d[f][k] + abs(i - k);
            q.push({-d[f][i], {f, i}});
          }
        }

  2. 选择升降电梯

    1
    2
    3
    4
    if (valid(f, k) && d[f + c[k]][k] > d[f][k] + abs(2 * c[k])) {
      d[f + c[k]][k] = d[f][k] + abs(2 * c[k]);
      q.push({-d[f + c[k]][k], {f + c[k], k}});
    }

SPFA实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int maxn = 30, maxm = 1e3 + 50;
int n, m, st;
// d[f][k]：层下标f槽下标k，求(1,st)到(n,...)的单源最短路
int c[maxn], d[maxm][maxn];
bool v[maxm][maxn];

bool valid(int f, int k) { return f + c[k] >= 1 && f + c[k] <= n; }

void spfa() {
  memset(d, 0x3f, sizeof(d));
  queue<pair<int, int>> q;
  d[1][st] = 0, v[1][st] = 1;
  q.push({1, st});
  while (!q.empty()) {
    int f = q.front().first, k = q.front().second;
    q.pop();
    v[f][k] = 0;
    // 改变槽的情况
    for (int i = 1; i <= m; ++i) {
      if (d[f][i] > d[f][k] + abs(i - k)) {
        d[f][i] = d[f][k] + abs(i - k);
        if (!v[f][i]) {
          v[f][i] = 1;
          q.push({f, i});
        }
      }
    }
    // 改变电梯的情况
    if (valid(f, k) && d[f + c[k]][k] > d[f][k] + abs(2 * c[k])) {
      d[f + c[k]][k] = d[f][k] + abs(2 * c[k]);
      if (!v[f + c[k]][k]) {
        v[f + c[k]][k] = 1;
        q.push({f + c[k], k});
      }
    }
  }
  int ans = 0x3f3f3f3f;
  for (int i = 1; i <= m; ++i) ans = min(ans, d[n][i]);
  cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> c[i];
    if (c[i] == 0) st = i;
  }
  spfa();
  return 0;
}

Dijkstra实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
const int maxn = 30, maxm = 1e3 + 50;
int n, m, st;
// d[f][k]：层下标f槽下标k，求(1,st)到(n,...)的单源最短路
int c[maxn], d[maxm][maxn];
bool v[maxm][maxn];

bool valid(int f, int k) { return f + c[k] >= 1 && f + c[k] <= n; }

void dijkstra() {
  memset(d, 0x3f, sizeof(d));
  priority_queue<pair<int, pair<int, int>>> q;
  d[1][st] = 0;
  q.push({0, {1, st}});
  while (!q.empty()) {
    int f = q.top().second.first, k = q.top().second.second;
    q.pop();
    if (v[f][k]) continue;
    v[f][k] = 1;
    // 改变槽的情况
    for (int i = 1; i <= m; ++i) {
      if (d[f][i] > d[f][k] + abs(i - k)) {
        d[f][i] = d[f][k] + abs(i - k);
        q.push({-d[f][i], {f, i}});
      }
    }
    // 改变电梯的情况
    if (valid(f, k) && d[f + c[k]][k] > d[f][k] + abs(2 * c[k])) {
      d[f + c[k]][k] = d[f][k] + abs(2 * c[k]);
      q.push({-d[f + c[k]][k], {f + c[k], k}});
    }
  }
  int ans = 0x3f3f3f3f;
  for (int i = 1; i <= m; ++i) ans = min(ans, d[n][i]);
  cout << (ans == 0x3f3f3f3f ? -1 : ans) << endl;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> c[i];
    if (c[i] == 0) st = i;
  }
  dijkstra();
  return 0;
}