网站如何做排名,网站开发公司排名,云南推广,深圳网站制作开发这里写自定义目录标题 更多精彩内容256题算法特训课#xff0c;帮你斩获大厂60W年薪offer 原题2023ICPC澳门真题传送B站动画详解 问题分析思路分析图的构建最短路径算法具体步骤 算法实现Dijkstra 算法图的构建 代码详解标准代码程序C代码Java代码Python代码Javascript代码 复… 这里写自定义目录标题 更多精彩内容256题算法特训课帮你斩获大厂60W年薪offer 原题2023ICPC澳门真题传送B站动画详解 问题分析思路分析图的构建最短路径算法具体步骤 算法实现Dijkstra 算法图的构建 代码详解标准代码程序C代码Java代码Python代码Javascript代码 复杂度分析时间复杂度空间复杂度 总结 更多精彩内容
这里是带你游历编程世界的Dashcoding编程社我是Dash/北航硕士/ICPC区域赛全国排名30/给你呈现我们眼中的世界
256题算法特训课帮你斩获大厂60W年薪offer
原题
2023ICPC澳门真题传送
B站动画详解
问题分析
题目要求从房间 0 0 0 到达房间 x x x 的最小能量消耗。可以进行两种操作传送到房间 ( i a i ) % n (i a_i) \% n (iai)%n 或者增加当前房间的数值 a i a_i ai。每次操作都消耗一点能量问题的本质是一个最短路径问题。
这个问题可以通过图论中的单源最短路径算法来解决。我们将每个房间视为图中的节点操作视为从一个节点到另一个节点的边求解从节点 0 0 0 到节点 x x x 的最短路径。
思路分析
图的构建 传送操作 如果在房间 i i i 进行传送操作可以跳到房间 ( i a i ) % n (i a_i) \% n (iai)%n。因此这个操作在图中表示为一条从节点 i i i 到节点 ( i a i ) % n (i a_i) \% n (iai)%n 的有向边权值为 1 1 1。 数值增加操作 如果选择增加房间的数值 a i ← a i 1 a_i \leftarrow a_i 1 ai←ai1则可以使得下次传送跳到下一个房间因此在图中可以加入一条从房间 i i i 到房间 i 1 i 1 i1 的边权值也为 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 (iai)%n这在图中表示为一条从节点 i i i 到节点 ( i a i ) % n (i a_i) \% n (iai)%n 的边。增加数值 a i a_i ai 后可以使得下一次传送跳到下一个房间。因此我们加入一条从节点 i i i 到节点 i 1 i 1 i1 的边。
另外为了处理房间 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;
vectorpairint,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_queuepairint,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 ComparablePair {int dist, node;Pair(int dist, int node) {this.dist dist;this.node node;}Overridepublic int compareTo(Pair other) {return Integer.compare(this.dist, other.dist);}}static final int N 100010;static ListPair[] 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);PriorityQueuePair 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 heapqdef dijkstra(st, n, G):dis [float(inf)] * (n 1)vis [False] * (n 1)dis[st] 0pq [(0, st)] # (distance, node)while pq:w, u heapq.heappop(pq)if vis[u]:continuevis[u] Truefor v, s in G[u]:if dis[v] w s:dis[v] w sheapq.heappush(pq, (dis[v], v))return disdef 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]) % nif to 0:to nG[i].append((to, 1))if i 1:to i 1if to n:to 1G[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 sortingconst [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((nm)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 算法来高效求解。算法的关键在于合理构建图结构并充分考虑不同操作的边权关系。通过引入虚拟节点处理特殊情况使得问题的求解更加简洁明了。这种图论思想在处理类似问题时具有广泛应用特别是在路径规划与最优决策问题中。
