P1565 最短路 - 题解

登录注册上岸

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

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

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

2025年8月31日 18:11

最短路（Floyd算法）题解：

P1565

回复 0 | 赞 0 | 浏览 105

#include<bits/stdc++.h> using namespace std; const int maxn = 100 + 5; const int INF = 1e9; // 使用一个较大的数避免溢出 int mp[maxn][maxn]; int n, m; void floyd(){ for(int k = 1; k <= n; k ++) { for(int i = 1; i <= n; i ++) { for(int j = 1; j <= n; j ++)...

2025年8月17日 14:03

最短路题解：迪杰斯特拉，用优先队列

P1565

回复 0 | 赞 0 | 浏览 100

#include <iostream> #include <vector> #include <algorithm> #include <iomanip> #include <set> #include <list> #include <string> #include <cmath> #include <stack> #include <map> #include <sstream> #include <queue> ...

2025年3月12日 17:05

最短路题解：Floyd & Dijkstra

P1565

回复 0 | 赞 7 | 浏览 494

// 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 | 浏览 604

#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 | 浏览 533

#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 | 浏览 540

#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 | 浏览 373

您好，我看高分篇说如果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 | 浏览 719

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.3k

#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 | 赞 10 | 浏览 943

稠密图用朴素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 &...

1
2

题目最短路

题解数量18

发布题解在线答疑

热门题解

1 1565 最短路 Dijkstra+去重边

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

3 SPFA以及自己踩的坑

4 最短路题解：Floyd & Dijkstra

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

6 最短路题解：floyd

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

8 SPFA

9 最短路题解：

10 P1565 最短路答疑提问：