这里写自定义目录标题
更多精彩内容
这里是带你游历编程世界的Dashcoding编程社，我是Dash/北航硕士/ICPC区域赛全国排名30+/给你呈现我们眼中的世界！
256题算法特训课，帮你斩获大厂60W年薪offer
原题
2023ICPC澳门真题传送
B站动画详解
问题分析
题目要求从房间 0 0 0 到达房间 x x x 的最小能量消耗。可以进行两种操作：传送到房间 ( i + a i ) % n (i + a_i) \% n (i+ai)%n 或者增加当前房间的数值 a i a_i ai。每次操作都消耗一点能量，问题的本质是一个最短路径问题。
这个问题可以通过图论中的单源最短路径算法来解决。我们将每个房间视为图中的节点，操作视为从一个节点到另一个节点的边，求解从节点 0 0 0 到节点 x x x 的最短路径。
思路分析
图的构建
传送操作：
如果在房间 i i i 进行传送操作，可以跳到房间 ( i + a i ) % n (i + a_i) \% n (i+ai)%n。因此，这个操作在图中表示为一条从节点 i i i 到节点 ( i + a i ) % n (i + a_i) \% n (i+ai)%n 的有向边，权值为 1 1 1。数值增加操作：
如果选择增加房间的数值 a i ← a i + 1 a_i \leftarrow a_i + 1 ai←ai+1，则可以使得下次传送跳到下一个房间，因此在图中可以加入一条从房间 i i i 到房间 i + 1 i + 1 i+1 的边，权值也为 1 1 1。特殊处理房间 0 0 0：
为了处理房间 0 0 0 的特殊情况（即只有在第二次及以后回到房间 0 0 0 时，才会从 0 0 0 引出一条边到 1 1 1），我们引入一个额外的节点 n n n，表示从 0 0 0 多次到达的状态。
最短路径算法
使用 Dijkstra 算法来计算从节点 0 0 0 到节点 x x x 的最短路径。Dijkstra 算法适用于具有非负权值的图，在该题中，每条边的权值为 1 1 1，正好符合该算法的要求。
具体步骤
- 初始化图，将每个节点与其对应的边构建好。
- 运行 Dijkstra 算法，计算从节点 0 0 0 出发到所有节点的最短路径。
- 输出节点 x x x 的最短距离，即为答案。
算法实现
Dijkstra 算法
Dijkstra 算法是一种贪心算法，用于解决单源最短路径问题。它通过优先队列（最小堆）来确保每次扩展的节点是当前距离最短的节点，从而保证计算出的路径是最优的。在本题中，我们将图中的每条边的权值设为 1 1 1，因此算法能够高效地计算最短路径。
图的构建
对于每个房间 i i i，我们有两种操作：
- 传送到房间 ( i + a i ) % n (i + a_i) \% n (i+ai)%n，这在图中表示为一条从节点 i i i 到节点 ( i + a i ) % n (i + a_i) \% n (i+ai)%n 的边。
- 增加数值 a i a_i ai 后，可以使得下一次传送跳到下一个房间。因此，我们加入一条从节点 i i i 到节点 i + 1 i + 1 i+1 的边。
另外，为了处理房间 0 0 0 的特殊情况，我们加入了一个节点 n n n，用来表示从房间 0 0 0 多次到达的状态。
代码详解
标准代码程序
C++代码
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int N = 1e5 + 10;
vector<pair<int,int>> G[N]; // 图的邻接表
int dis[N], a[N], vis[N], n, x;
// Dijkstra 算法求单源最短路径
void dij(int st, int *dis) {
for(int i = 0; i <= n; i++) {
vis[i] = 0;
dis[i] = INT_MAX;
}
priority_queue<pair<int,int>> q;
dis[st] = 0;
q.push({0, st});
while(q.size()) {
int w = -q.top().first;
int u = q.top().second;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(auto v : G[u]) {
int to = v.first;
int s = v.second;
if(dis[to] > w + s) {
dis[to] = w + s;
q.push({-dis[to], to});
}
}
}
}
int main() {
cin >> n >> x;
for(int i = 0; i < n; i++) cin >> a[i];
// 构建图
for(int i = 0; i <= n; i++) {
int to = (i + a[i % n]) % n;
if(to == 0) to = n; // 处理到达 0 的情况
G[i].push_back({to, 1});
if(i >= 1) { // 增加数值后的操作
to = i + 1;
if(to > n) to = 1;
G[i].push_back({to, 1});
}
}
// 运行 Dijkstra 算法
dij(0, dis);
// 输出结果
cout << dis[x];
}
Java代码
import java.util.*;
public class Main {
static class Pair implements Comparable<Pair> {
int dist, node;
Pair(int dist, int node) {
this.dist = dist;
this.node = node;
}
@Override
public int compareTo(Pair other) {
return Integer.compare(this.dist, other.dist);
}
}
static final int N = 100010;
static List<Pair>[] G = new ArrayList[N];
static int[] dis = new int[N], a = new int[N], vis = new int[N];
static int n, x;
static void dijkstra(int st) {
Arrays.fill(vis, 0);
Arrays.fill(dis, Integer.MAX_VALUE);
PriorityQueue<Pair> pq = new PriorityQueue<>();
dis[st] = 0;
pq.add(new Pair(0, st));
while (!pq.isEmpty()) {
Pair p = pq.poll();
int w = p.dist, u = p.node;
if (vis[u] == 1) continue;
vis[u] = 1;
for (Pair v : G[u]) {
int to = v.node, s = v.dist;
if (dis[to] > w + s) {
dis[to] = w + s;
pq.add(new Pair(dis[to], to));
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
x = sc.nextInt();
for (int i = 0; i <= n; i++) G[i] = new ArrayList<>();
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
for (int i = 0; i <= n; i++) {
int to = (i + a[i % n]) % n;
if (to == 0) to = n;
G[i].add(new Pair(1, to));
if (i >= 1) {
to = i + 1;
if (to > n) to = 1;
G[i].add(new Pair(1, to));
}
}
dijkstra(0);
System.out.println(dis[x]);
}
}
Python代码
import heapq
def dijkstra(st, n, G):
dis = [float('inf')] * (n + 1)
vis = [False] * (n + 1)
dis[st] = 0
pq = [(0, st)] # (distance, node)
while pq:
w, u = heapq.heappop(pq)
if vis[u]:
continue
vis[u] = True
for v, s in G[u]:
if dis[v] > w + s:
dis[v] = w + s
heapq.heappush(pq, (dis[v], v))
return dis
def main():
n, x = map(int, input().split())
a = list(map(int, input().split()))
G = [[] for _ in range(n + 1)]
for i in range(n):
to = (i + a[i % n]) % n
if to == 0:
to = n
G[i].append((to, 1))
if i >= 1:
to = i + 1
if to > n:
to = 1
G[i].append((to, 1))
dis = dijkstra(0, n, G)
print(dis[x])
if __name__ == "__main__":
main()
Javascript代码
function dijkstra(st, n, G) {
const dis = Array(n + 1).fill(Infinity);
const vis = Array(n + 1).fill(false);
const pq = [[0, st]]; // [distance, node]
dis[st] = 0;
while (pq.length) {
pq.sort((a, b) => b[0] - a[0]); // Max-heap simulated with sorting
const [w, u] = pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (const [v, s] of G[u]) {
if (dis[v] > w + s) {
dis[v] = w + s;
pq.push([dis[v], v]);
}
}
}
return dis;
}
function main() {
const [n, x] = prompt().split(' ').map(Number);
const a = prompt().split(' ').map(Number);
const G = Array.from({ length: n + 1 }, () => []);
for (let i = 0; i < n; i++) {
let to = (i + a[i % n]) % n;
if (to === 0) to = n;
G[i].push([to, 1]);
if (i >= 1) {
to = i + 1;
if (to > n) to = 1;
G[i].push([to, 1]);
}
}
const dis = dijkstra(0, n, G);
console.log(dis[x]);
}
main();
复杂度分析
时间复杂度
Dijkstra 算法的时间复杂度为 O ( ( n + m ) log n ) O((n + m) \log n) O((n+m)logn)，其中 m m m 是边的数量。在本题中，图中的边数量近似为 2 n 2n 2n，所以复杂度为 O ( n log n ) O(n \log n) O(nlogn)。
空间复杂度
图的存储空间为 O ( n ) O(n) O(n)，距离数组和访问标记数组的空间也为 O ( n ) O(n) O(n)，因此总体空间复杂度为 O ( n ) O(n) O(n)。
总结
本题通过将问题转化为图论中的最短路径问题，并使用 Dijkstra 算法来高效求解。算法的关键在于合理构建图结构，并充分考虑不同操作的边权关系。通过引入虚拟节点，处理特殊情况，使得问题的求解更加简洁明了。这种图论思想在处理类似问题时具有广泛应用，特别是在路径规划与最优决策问题中。