ZHLin_Blog
课程报告：Dijkstra 算法与大数据应用
返回首页
搜索
课程报告：Dijkstra 算法与大数据应用
发表于
2026-05-26
|
更新于
2026-10-16
|
课程报告
|
浏览量:
请输入访问密码
解密
文章作者:
ZHLin
文章链接:
https://zhlblog.top/2026/05/26/Dijkstra%E7%AE%97%E6%B3%95%E4%B8%8E%E5%A4%A7%E6%95%B0%E6%8D%AE%E5%BA%94%E7%94%A8/
版权声明:
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议。转载请注明来源
ZHLin_Blog
！
上一篇
南京晓庄学院第一次月赛
P14584 [LNCPC 2025] 点击平衡球 题目背景 Z 形管道猫推荐您来玩平衡球（Ballance）。在游戏中，玩家要操纵一个可以改变自身材质（即物理性质）的球在由路面和机关构成的庞大而复杂的迷宫建筑中穿梭，避开陷阱、运用机关并破解一个个谜题，最终到达终点。 题目描述 平衡球有
3
3
3
种材质（纸球、木球、石球）。在游戏中，平衡球需要通过
n
n
n
个机关，每个机关各自只允许特定一些材质的平衡球通过。初始，您需要花费
1
1
1
单位的代价将平衡球选定为一种材质。在通过每个机关前，您可以花费
1
1
1
单位的代价将平衡球切换为另一种材质，也可以不花费代价保持当前材质。 现在您可以任意安排机关的通过顺序，请您求出平衡球通过这
n
n
n
个机关所需的最小代价。 输入格式 第一行给定一个整数
n
(
1
≤
n
≤
100
)
n(1\le n\le 100)
n
(
1
≤
n
≤
100
)
，表示机关总数。 接下来
n
n
n
行，每行给定三个整数
a
i
,
1
,
a
i
,
2
,
a
i
,
3
(
a
i
,
1
,
a
i
,
2
,
a
i
,
3
∈
{
0
,
1
}
)
a_{i,1},a_{i,2},a_{i,3}(a_{i,1},a_{i,2},a_{i,3}\in\{0,1\})
a
i
,
1
,
a
i
,
2
,
a
i
,
3
(
a
i
,
1
,
a
i
,
2
,
a
i
,
3
∈
{
0
,
1
})
，其中第
i
i
i
行的第
j
j
j
个整数
a
i
,
j
a_{i,j}
a
i
,
j
为
0
0
0
、
1
1
1
分别表示给定的第
i
i
i
个机关不允许、允许第
j
j
j
种材质的平衡球通过。保证
a
i
,
1
,
a
i
,
2
,
a
i
,
3
a_{i,1},a_{i,2},a_{i,3}
a
i
,
1
,
a
i
,
2
,
a
i
,
3
不全为
0
0
0
。 输出格式 一个整数，表示经由合理安排机关的通过顺序和材质的代价花费，平衡球通过这
n
n
n
个机关所需的最小代价。 输入输出样...
下一篇
Dijkstra算法
邻接矩阵存储 适用情况：稠密图，即边数 E 接近顶点数 V 的平方时，空间利用率高。 时间复杂度：
O
(
n
2
)
O(n^2)
O
(
n
2
)
空间复杂度：
O
(
n
2
)
O(n^2)
O
(
n
2
)
邻接矩阵存储写法 #include <bits/stdc++.h>using namespace std;const int N = 510;int n, m, x, y, z;int a[N][N], dis[N];bool vis[N];int dijkstra(){ //因为要找最近的点，所以所有点距离1点距离初始化为极大值 memset(dis, 0x3f, sizeof dis); //标记第一个点距离1号点距离为0 dis[1] = 0; //vis[1] = true加上这行第一次循环就标记不出t for (int i = 1; i <= n; i++) { //寻找未访问的最近点 int t = -1; for (int j = 1; j <= n; j++) if (!vis[j] && (t == -1 || dis[j] < dis[t])) t = j; ...
评论
ZHLin
技术博客，记录学习过程
文章
33
分类
6
我的说说
公告
洛谷团队链接: https://www.luogu.com.cn/team/118658
最新文章
大一算法竞赛获奖记录（2025—2026）
2026-10-16
Yolov5 train.py main()函数解析
2026-10-16
洛谷蓝桥杯国赛模拟
2026-05-31
2026“钉耙编程”中国大学生算法设计春季联赛（4）
2026-05-26
2026“钉耙编程”中国大学生算法设计春季联赛（5）
2026-05-26
搜索
数据加载中
