P1565 最短路 - 题解

登录注册上岸

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

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

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

2022年7月20日 13:20

1565 最短路 Dijkstra+去重边

P1565

回复 2 | 赞 5 | 浏览 6.7k

这题本质上就是经典的朴素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 | 赞 2 | 浏览 2.7k

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

2022年6月30日 20:00

SPFA

P1565

回复 2 | 赞 1 | 浏览 5.3k

#include <iostream> #include <queue> #define INF 1000000 using namespace std; int n,m; const int maxn = 105; // 图 int gra[maxn][maxn]; // 保存最短路径值。dist[i]表示起点到i点的最短路径值 int dist[maxn]; // 标记。vis[i]=1表示节点i在队列中，vis[i]=0表示不在队列中 int vis[maxn]; void spfa(int s){ // 初...

2023年5月3日 22:24

最短路题解：

P1565

回复 0 | 赞 1 | 浏览 1.1k

思路分析最短路模板题，有两个注意点一次，多组数据，注意对数组的清空。无向图，建图的时候注意要add正反两次。每次都要初始化 void init() { memset(h,-1,sizeof h); memset(vis,0,sizeof vis); memset(dis,0x3f,sizeof dis); idx = 0; } spfa 起始点为1，终点为n。 auto spfa = [&]()->void { queue<int> q; q.p...

2023年1月14日 23:21

堆优化dijkstra及Floyd

P1565

回复 0 | 赞 1 | 浏览 3.0k

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=300086; typedef pair<int, int> PII; int n,m; // 点的数量 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储所有点到1号点的距离 bool st[N]; // 存储每个点的最短距离是否已确定 void add(in...

2021年2月26日 16:41

朴素dijkstra以及堆优化dijkstra 注意重边无向图

P1565

回复 0 | 赞 0 | 浏览 7.9k

#include <bits/stdc++.h> using namespace std; const int N = 110; int n, m; int g[N][N]; int d[N]; bool st[N]; int dijkstra() { memset(d, 0x3f, sizeof d); d[1] = 0; for(int i = 0; i < n; i++) { int t = -1; for (int j = 1; j <= n; j+...

2021年2月18日 20:07

Dijkstra 可能有重边

P1565

回复 0 | 赞 0 | 浏览 7.7k

#include <iostream> #include <algorithm> #include <string.h> using namespace std; const int maxn=105; int g[maxn][maxn]; int dist[maxn]; int vis[maxn]; int n,m; int dijkstra(){ dist[1]=0; for(int i=1;i<=n;i++){ ...

2021年1月26日 10:54

打卡

P1565

回复 0 | 赞 0 | 浏览 8.3k

#include<iostream> #include<string> #include<string.h> #include<vector> #include<stdio.h> #include <queue> #include<algorithm> using namespace std; const int maxn=205; vector<pair<int,int>>E[maxn]; int n,m; int d[maxn],inq[maxn]...

题目最短路

题解数量8

热门题解

1 1565 最短路 Dijkstra+去重边

2 SPFA以及自己踩的坑

3 堆优化dijkstra及Floyd

4 最短路题解：

5 SPFA

6 朴素dijkstra以及堆优化dijkstra 注意重边无向图

7 打卡

8 Dijkstra 可能有重边