达州网站开发qinsanw,湖南网站建设哪家有,深圳有做网站的公司有哪些,如何用付费音乐做视频网站知识概览 Dijkstra算法适用于解决所有边权都是正数的最短路问题。Dijkstra算法分为朴素的Dijkstra算法和堆优化版的Dijkstra算法。朴素的Dijkstra算法时间复杂度为#xff0c;适用于稠密图。堆优化版的Dijkstra算法时间复杂度为#xff0c;适用于稀疏图。稠密图的边数m和是一…知识概览 Dijkstra算法适用于解决所有边权都是正数的最短路问题。Dijkstra算法分为朴素的Dijkstra算法和堆优化版的Dijkstra算法。朴素的Dijkstra算法时间复杂度为适用于稠密图。堆优化版的Dijkstra算法时间复杂度为适用于稀疏图。稠密图的边数m和是一个级别的稀疏图的边数m和点数n是一个级别的。 朴素的Dijkstra算法
例题展示
题目链接
活动 - AcWing系统讲解常用算法与数据结构给出相应代码模板并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/description/851/
代码
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 510;int n, m;
int g[N][N];
int dist[N];
bool st[N];int dijkstra()
{// dist[1] 0, dist[i] 无穷大memset(dist, 0x3f, sizeof dist);dist[1] 0;for (int i 0; i n - 1; i){int t -1;for (int j 1; j n; j)if (!st[j] (t -1 || dist[t] dist[j]))t j; // t为不在st为false的距离最近的点st[t] true;// 用t更新其它点的距离for (int j 1; j n; j)dist[j] min(dist[j], dist[t] g[t][j]);}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main()
{scanf(%d%d, n, m);memset(g, 0x3f, sizeof g);while (m--){int a, b, c;scanf(%d%d%d, a, b, c);g[a][b] min(g[a][b], c); // 重边取最小距离}int t dijkstra();printf(%d\n, t);return 0;
} 堆优化版的Dijkstra算法
例题展示
题目链接
活动 - AcWing系统讲解常用算法与数据结构给出相应代码模板并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/852/
代码
#include cstring
#include iostream
#include algorithm
#include queueusing namespace std;typedef pairint, int PII;const int N 150010;int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;priority_queuePII, vectorPII, greaterPII heap;heap.push({0, 1});while (heap.size()){auto t heap.top();heap.pop();int ver t.second, distance t.first;if (st[ver]) continue;st[ver] true;for (int i h[ver]; i ! -1; i ne[i]){int j e[i];if (dist[j] distance w[i]){dist[j] distance w[i];heap.push({dist[j], j});}}}if (dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main()
{scanf(%d%d, n, m);memset(h, -1, sizeof h);while (m--){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}int t dijkstra();printf(%d\n, t);return 0;
} 参考资料
AcWing算法基础课
