P1666 好坑的电子地图 - 题解

登录注册上岸

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

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

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

2026年3月23日 20:12

好坑的电子地图在评论区floyd同学上改进题解：

P1666

回复 0 | 赞 0 | 浏览 26

#include<bits/stdc++.h> using namespace std; const int n = 1e3 + 9; int dis[n][n]; int extime(int x) { if(x % 2 == 0) return 2; else return 1; } int main() { ios::sync_with_stdio(0); cin.tie(0); int N, M, S, T, A; while(cin >> N >> M >> S...

2026年3月17日 22:13

好坑的电子地图题解：C语言-Dijkstra的变种（结点含有惩罚时间

P1666

回复 0 | 赞 2 | 浏览 38

#include<stdio.h> #include<stdlib.h> #define INF 0x3f3f3f3f #define maxsize 1000 int Edge[maxsize][maxsize]; //邻接矩阵 int numedg, numvex;//边数、顶点数 int getWaitTime(int u) { //获得结点的惩罚时间 if (u % 2 == 1)return 1; return 2; } void Dijk...

2025年3月19日 23:34

好坑的电子地图题解：

P1666

回复 0 | 赞 4 | 浏览 943

分析题意,本题是求最短路径的题目,考虑使用迪杰斯特拉。本题的变化点在于奇数结点所连边需要权值加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 | 赞 2 | 浏览 3.7k

#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 | 赞 2 | 浏览 4.6k

思路：广度优先搜索。队列记录路径节点，奇数点+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 | 赞 1 | 浏览 8.0k

#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 | 赞 7 | 浏览 10.5k

#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...

题目好坑的电子地图

题解数量7

发布题解在线答疑

热门题解

1 迪杰斯特拉算法

2 好坑的电子地图题解：

3 朴素BFS

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

5 好坑的电子地图题解：C语言-Dijkstra的变种（结点含有惩罚时间）

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

7 好坑的电子地图在评论区floyd同学上改进题解：