P1666 好坑的电子地图 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2025年3月19日 23:34

好坑的电子地图题解：

P1666

回复 0 | 赞 1 | 浏览 205

分析题意,本题是求最短路径的题目,考虑使用迪杰斯特拉。本题的变化点在于奇数结点所连边需要权值加1，偶数结点所连边权值加2，故我们可以在邻接矩阵初始化的时候就把这个权值加入进去,而求最短路径的具体实现就是迪杰斯特拉算法的思想了。具体代码实现如下： #include <bits/stdc++.h> using namespace std; int Graph[1000][1000];//邻接矩阵存储图 int vis[1000];//标记是否被求得最短路径 int dis[1000];//用于保存源点到各个点的最短路径 // 求单源最短路径用迪杰斯特拉 ...

2023年2月9日 20:26

弗洛伊德算法求出各点间的最短距离和最佳路径

P1666

回复 0 | 赞 1 | 浏览 3.3k

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF=1e9; int n,m,S,T,A; int mp[1001][1001];//存储图像 string path[1001][1001]; //以字符串的方式记录每个点之间的最佳路径 string name[1001];//记录顶点 void floyd(){ //弗洛伊德函数 for(int i=1;i<=n;i++){ ...

2022年5月29日 10:42

朴素BFS

P1666

回复 0 | 赞 1 | 浏览 4.3k

思路：广度优先搜索。队列记录路径节点，奇数点+1，偶数点+2，走到goal时结束搜索。 #include <bits/stdc++.h> using namespace std; typedef struct node { int num; int sum; node() {} node(int num, int sum) { this->num = num; this->sum = sum; } } node; int main() { ...

2020年5月11日 11:19

求最帅的指出一下spfa50%ac

P1666

回复 0 | 赞 0 | 浏览 7.6k

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <vector> #include <queue> using namespace std; int n,m,s,t,a; const int maxn=1001; struct edge{ int u,v,w; edge(int u,int v,int w):u(u...

我要上华工

2020年3月25日 22:29

迪杰斯特拉算法

P1666

回复 0 | 赞 5 | 浏览 10.2k

#include<iostream> #include<stack> #include<string> #include<queue> #include<map> #include<vector> #include<cmath> #include<algorithm> #include<cstring> #include<set> using namespace std; #define MAXX 1010 #define INFF 0x3f...

题目好坑的电子地图

题解数量5

发布题解在线答疑

热门题解

1 迪杰斯特拉算法

2 朴素BFS

3 弗洛伊德算法求出各点间的最短距离和最佳路径

4 好坑的电子地图题解：

5 求最帅的指出一下spfa50%ac