P1565 最短路 - 题解

登录注册上岸

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

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

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

2026年3月13日 18:03

最短路题解：C语言Dijkstra算法解法

P1565

回复 0 | 赞 2 | 浏览 17

#include<stdio.h> #include<stdlib.h> #define maxsize 200 #define INF 0x3f3f3f3f typedef struct { int numvex, numedg; int Egde[maxsize][maxsize]; int verticles[maxsize]; }Graph; void Dijkstra(Graph G,int u,int end) { ...

2026年3月13日 17:27

最短路题解：

P1565

回复 0 | 赞 0 | 浏览 8

#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; const int N = 105; struct Edge{ int from; int to; int weight; }; int dist[N]; bool vis[N]; vector<Edge>e[N]; void SPFA(int s){ memset...

2026年3月7日 20:12

最短路题解：SPFA+vector邻接表

P1565

回复 0 | 赞 3 | 浏览 33

#include <bits/stdc++.h> using namespace std; /* spfa+vector */ #define INF 0x3f3f3f3f const int Max = 105; int n,m; struct Edge { int u, v,w; }; vector<Edge> edges; vector<int> G[Max]; int dist[Max]; int vis[Max]; void SPFA(int s) { for (int i =...

2025年8月31日 18:11

最短路（Floyd算法）题解：

P1565

回复 0 | 赞 8 | 浏览 814

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

#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 | 赞 8 | 浏览 899

// 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 | 浏览 1.1k

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

#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 | 赞 8 | 浏览 922

#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 | 赞 3 | 浏览 861

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

1
2
3

题目最短路

题解数量21

发布题解在线答疑

热门题解

1 1565 最短路 Dijkstra+去重边

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

3 SPFA以及自己踩的坑

4 最短路题解：Floyd & Dijkstra

5 最短路（Floyd算法）题解：

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

7 最短路题解：floyd

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

9 SPFA

10 最短路题解：SPFA+vector邻接表