搜索结果
查询Tags标签： 号点，共有 14条记录-
cf550 D. Regular Bridge
题意： 给定 \(k\)，构造连通、无重边、无自环、每个点的度为 \(k\) 且含至少一个桥的无向无权图 \(1\le k \le 100\) 思路： 当 \(k\) 为偶数时无解：设 \(k=2s\)，设某连通块 \(G\) 与图的其他部分通过桥 \(e\) 连接，去掉桥 \(e\)，则 \(G\) 中有一个点的度为 \(2s-1\)…
2022/6/6 23:23:02 人评论 次浏览 -
ARC103E题解
题面 题意： 给你一个长度为 \(n\) 的 01 串 \(S\) ，要求构造一颗 \(n\) 个点的树。 要求： 当 \(S_i=1\) 时，存在一条边，使得若它被切断时，生成的森林中有一棵树的节点数为 \(i\) 。 当 \(S_i=0\) 时，不存在一条边，使得若它被切断时，生成的森林中有一棵树的节点数…
2022/4/6 23:25:35 人评论 次浏览 -
最短路
最短路难点不在于证明，在于建图，把一个问题抽象成图，如何定义边，如何定义图Dijkstra迪杰斯特拉 本质，是不断刷新起点与其他各个顶点之间的 “距离表”。初始化距离一号结点的距离为零，其他结点的距离设为无穷大（看具体的题）。 循环n次，每一次将集合S之外距离最短…
2022/3/22 6:30:04 人评论 次浏览 -
最短路算法
单源最短路 正权边 Dijkstra算法 O(n^2)每次通过已知最短距离来更新到其他点的最短路 注意出现重边要进行比较#include<iostream> #include<algorithm> using namespace std; const int N = 1e5+10; int g[N][N];//邻接矩阵 int dist[N];//源点到其他点的距离…
2022/3/20 11:27:56 人评论 次浏览 -
Dijkstra求最短路算法 ( 超级超级详细的 ) 不断更新中
接下来给出模板 朴素版dijkstra算法 时间复杂是 O(n^2+m), n 表示点数，m 表示边数 int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1 int dijkst…
2021/12/26 12:07:08 人评论 次浏览 -
Dijkstra求最短路算法 ( 超级超级详细的 ) 不断更新中
接下来给出模板 朴素版dijkstra算法 时间复杂是 O(n^2+m), n 表示点数，m 表示边数 int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1 int dijkst…
2021/12/26 12:07:08 人评论 次浏览 -
acwing 849 Dijkstra求最短路
给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环，所有边权均为正值。 请你求出 11 号点到 nn 号点的最短距离，如果无法从 11 号点走到 nn 号点，则输出 −1−1。 输入格式 第一行包含整数 nn 和 mm。 接下来 mm 行每行包含三个整数 x,y,zx,y,z，表示存在一条…
2021/12/7 23:47:37 人评论 次浏览 -
acwing 849 Dijkstra求最短路
给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环，所有边权均为正值。 请你求出 11 号点到 nn 号点的最短距离，如果无法从 11 号点走到 nn 号点，则输出 −1−1。 输入格式 第一行包含整数 nn 和 mm。 接下来 mm 行每行包含三个整数 x,y,zx,y,z，表示存在一条…
2021/12/7 23:47:37 人评论 次浏览 -
【JAVA】无向连通图到达所有点必须经过固定点成本之和的最小值（Pro20210903）（Dijkstra + DP）
【JAVA】无向连通图到达所有点必须经过固定点成本之和的最小值（Pro20210903）（Dijkstra + DP） 题目思路代码题目 略 思路 每次到达下一个点必须经过1号店，可以拆解为从当前点到1号点的最短路径，加上从1号点到目的地的最短路径。 也就是说，整个过程可以分解为： 1号点…
2021/9/8 11:06:04 人评论 次浏览 -
【JAVA】无向连通图到达所有点必须经过固定点成本之和的最小值（Pro20210903）（Dijkstra + DP）
【JAVA】无向连通图到达所有点必须经过固定点成本之和的最小值（Pro20210903）（Dijkstra + DP） 题目思路代码题目 略 思路 每次到达下一个点必须经过1号店，可以拆解为从当前点到1号点的最短路径，加上从1号点到目的地的最短路径。 也就是说，整个过程可以分解为： 1号点…
2021/9/8 11:06:04 人评论 次浏览 -
算法题解 ----堆优化版的Dijsktra算法
题目要求: 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。 输入格式 第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 …
2021/8/21 1:36:16 人评论 次浏览 -
算法题解 ----堆优化版的Dijsktra算法
题目要求: 给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。 输入格式 第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 …
2021/8/21 1:36:16 人评论 次浏览 -
基础课复习之图论
基础课图论复习-最短路朴素Dijkstra算法 (适合稠密图 用邻接矩阵存图) 时间复杂度 O(\(n^2 + m\)) n表示点数， m表示边数 AcWing 849. Dijkstra求最短路Iint g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路…
2021/8/14 6:06:16 人评论 次浏览 -
基础课复习之图论
基础课图论复习-最短路朴素Dijkstra算法 (适合稠密图 用邻接矩阵存图) 时间复杂度 O(\(n^2 + m\)) n表示点数， m表示边数 AcWing 849. Dijkstra求最短路Iint g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路…
2021/8/14 6:06:16 人评论 次浏览
