ให้มองว่าแต่ละชั้นคือ Vertex และสะพานคือ Edge โดยข้อนี้เป็น Weighted Directed Graph เนื่องจากสะพานเป็นสะพานทางเดียวและทุกๆ Edge มี Weight คือพลังงานที่ใช้ซึ่งก็คือ 1

วิธีที่ 1 Shortest Path

เราสามารถคำนวณพลังงานน้อยที่สุดที่ใช้ในการขึ้นจากชั้นที่ $1$ ไปยังชั้นที่ $i$ โดยใช้ Dijkstra's Algorithm

โดยอาจจะใช้ BFS (Breadth-first search) แทน Dijkstra's Algorithm ได้เพราะ Weight ของ Edge ทุกเส้นเท่ากันหมด

วิธีที่ 2 Dynamic Programming

นิยามให้ $dp[i]$ คือค่าพลังงานที่น้อยที่สุดที่สามารถขึ้นไปถึงชั้นที่ $i$ ได้ แสดงว่า $dp[1] = 0$ เนื่องจากเป็นชั้นเริ่มต้น ถ้าให้ชั้นที่ $j_{1}, j_{2}, ...$ มีสะพานที่ขึ้นมาชั้นที่ $i$ ได้ เราจะสามารถเขียนเป็นสมการได้ว่า

$dp[i] = \min(dp[j_{k}] + 1)$ เมื่อ $k = 1, 2, ...$

เมื่อคำนวณทุกชั้นเสร็จแล้วเราจะหาคำตอบโดยพิจารณาหา $i$ ที่มากที่สุดที่ทำให้ $dp[i] \leq k$

Solution Code 1

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> ii;

const int MXN = 1e4 + 5;
const int INF = 1e9 + 7;

vector<int> edge[MXN];
int dp[MXN];

int main() {
  int k, n, m;
  scanf("%d %d %d", &k, &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    edge[a].push_back(b);
  }
  for (int i = 1; i <= n; i++) {
    dp[i] = INF;
  }
  dp[1] = 0;
  priority_queue<ii, vector<ii>, greater<ii>> pq;
  pq.emplace(dp[1], 1);
  while (pq.size()) {
    int u = pq.top().second;
    pq.pop();
    for (auto i : edge[u]) {
      if (dp[i] > dp[u] + 1) {
        dp[i] = dp[u] + 1;
        pq.emplace(dp[i], i);
      }
    }
  }
  for (int i = n; i >= 1; i--) {
    if (dp[i] <= k) {
      printf("%d", i);
      return 0;
    }
  }
}

Time Complexity $\mathcal{O}(M\log{}(N) + N)$

Solution Code 2

#include <bits/stdc++.h>

using namespace std;
const int MXN = 1e4 + 5;
const int INF = 1e9 + 7;

vector<int> edge[MXN];
int dp[MXN];

int main() {
  int k, n, m;
  scanf("%d %d %d", &k, &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    edge[a].push_back(b);
  }
  for (int i = 1; i <= n; i++) {
    dp[i] = INF;
  }
  dp[1] = 0;
  for (int i = 1; i <= n; i++) {
    for (auto j : edge[i]) {
      dp[j] = min(dp[j], dp[i] + 1);
    }
  }
  for (int i = n; i >= 1; i--) {
    if (dp[i] <= k) {
      printf("%d", i);
      return 0;
    }
  }
}

Time Complexity $\mathcal{O}(M + N)$