P1565 最短路 - 题解

登录注册上岸

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

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

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

2025年3月12日 17:05

最短路题解：Floyd & Dijkstra

P1565

回复 0 | 赞 7 | 浏览 415

// 17:01 // #include <bits/stdc++.h> #include <iostream> using namespace std; #define INF 0x0fffffff #define MAXN 1001 int n, m; typedef struct MGraph { int edge[MAXN][MAXN]; //int n; ...

2025年2月28日 16:30

最短路题解：floyd with 打印路径

P1565

回复 0 | 赞 5 | 浏览 516

#include <iostream> #include <queue> using namespace std; #define INF 0x3f3f3f3f const int N = 1005; struct Edge { int b, c; }; int n, m, pre[N][N]; void floyd(int d[105][105]) { for (int k = 1; k <= n; k++) { ...

2025年2月28日 12:50

最短路题解：floyd

P1565

回复 0 | 赞 5 | 浏览 406

#include <iostream> #include <queue> using namespace std; #define INF 0x3f3f3f3f const int N = 1005; struct Edge { int b, c; }; int n, m; void floyd(int d[105][105]) { for (int k = 1; k <= n; k++) { for (int i...

2025年2月28日 11:18

最短路题解：堆优化的dijkstra

P1565

回复 0 | 赞 7 | 浏览 449

#include <iostream> #include <queue> using namespace std; #define INF 0x3f3f3f3f const int N = 1005; struct Edge { int b, c; }; int n, m; void dijkstra(int s, int dis[], int vis[], vector<Edge> g[], int pre[]) { // 初始化 f...

2025年2月23日 21:05

P1565 最短路答疑提问：

P1565

回复 1 | 赞 2 | 浏览 260

您好，我看高分篇说如果spfa超时可以改成优先队列，请问一下是这样改吗原版： #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f const int N = 1005; struct Edge { int b, c; }; int n, m; void spfa(int s, int dis[], int vis[], vector<Edge> g[], int pre[]) { &nbs...

2025年2月23日 20:57

最短路题解：

P1565

回复 0 | 赞 2 | 浏览 582

queue实现spfa #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f const int N = 1005; struct Edge { int b, c; }; int n, m; void spfa(int s, int dis[], int vis[], vector<Edge> g[], int pre[]) { for (int i = 1; i <= n; ...

2025年2月23日 19:43

P1565 最短路答疑提问：

P1565

回复 0 | 赞 0 | 浏览 1.2k

#include<bits/stdc++.h> using namespace std; #define max1 10000000 const int maxn=1000; int gmap[maxn][maxn]; int visited[maxn]; int dist[maxn]; int dj(int n){//n表示n结点 dist[1] = 0; //先初始化dist数组 for(int i = 2;i<=n;i++){ if(gmap[1][i]>0){ dist[i] = gmap[1...

2025年1月13日 15:59

最短路 (朴素Dijkstra)题解：

P1565

回复 0 | 赞 9 | 浏览 699

稠密图用朴素Dijkstra算法，用链式前向星存储图 #include<bits/stdc++.h> using namespace std; const int N = 110; int g[N][N]; int dist[N]; bool st[N]; int n, m; int dijkstra() { for(int i = 2; i <= n; i ++) dist[i] = INT_MAX / 2; dist[1] = 0; for(int i = 0; i &...

2022年7月20日 13:20

1565 最短路 Dijkstra+去重边

P1565

回复 2 | 赞 19 | 浏览 7.9k

这题本质上就是经典的朴素Dijkstra算法使用 G[MAXN][MAXN]邻接矩阵表示图 vis[MAXN]表示点是否被标记 dis[MAXN]表示源点到点i的最短距离 pre[MAXN]表示点i的前向点根据Dijkstra算法，进行迭代即可。关于Dijkstra算法的理解，这里推荐一个视频：Dijkstra算法视频展示这题的坑在于：有重边！即可能出现多次输入点a和点b之间的路径权值，且每次输入权值不一样。这时候就需要去重，取输入权值最小的一次即可，否则通过率只有33% 去重代码： ...

努力努力在努力

2023年2月24日 18:52

SPFA以及自己踩的坑

P1565

回复 2 | 赞 8 | 浏览 3.2k

#include <algorithm> #include <bits/stdc++.h> #include <cmath> #include <cstdio> #include <cstdlib> #include <math.h> #include <queue> #include <string> using namespace std; #define MAX 100000 int gra[105][105]...

1
2

题目最短路

题解数量16

发布题解在线答疑

热门题解

1 1565 最短路 Dijkstra+去重边

2 最短路 (朴素Dijkstra)题解：

3 SPFA以及自己踩的坑

4 最短路题解：Floyd & Dijkstra

5 最短路题解：堆优化的dijkstra

6 最短路题解：floyd

7 最短路题解：floyd with 打印路径

8 SPFA

9 最短路题解：

10 P1565 最短路答疑提问：