企业官网建设流程全解析

wordpress文本框,wordpress中文网站优化,在线网站设计工具,视频推广的好处【题目来源】 https://oj.czos.cn/p/2379 https://www.acwing.com/problem/content/852/ 【题目描述】 Mar 星球上共有 n 个城市#xff08;编号为 1~n#xff09;#xff0c;城市之间为了方便交通修建了 m 条单向高速公路。 有些公路是为了交通方便连接了 2 个不同的城市编号为 1~n城市之间为了方便交通修建了 m 条单向高速公路。有些公路是为了交通方便连接了 2 个不同的城市有些公路是为了观光方便从一个城市出发最后还会回到该城市。两个城市之间、以及从本市出发回本市的道路都可能有多条。作为交通部新来的程序员你接到了一个第一个任务已知所有道路起止点以及走该条路需要花的过路费计算出从 1 号城市到 n 号城市的最低花费【输入格式】第 1 行有 2 个整数 n 和 m1≤n, m≤10^5接下来 m 行每行有 3 个整数 u、v、p表示从有一条道路从 u 市连到 v 市走该条路需要花费 p 元。1≤u, v≤n1≤p≤10^4)。​​​​​​​【输出格式】输出一个整数代表从 1 号城市到 n 号城市的最少交通费。如果根据给定的数据发现从 1 号城市无法到达 n 号城市请输出 -1。​​​​​​​【输入样例】3 41 2 11 3 32 3 11 1 2【输出样例】2【数据范围】1≤n, m≤10^51≤u, v≤n1≤p≤10^4【算法分析】● Dijkstra 算法Dijkstra 算法是一种用于解决有权图中单源最短路径问题的经典算法由荷兰计算机科学家 Edsger W. Dijkstra 于 1956 年提出。以下是该算法的核心要点1适用范围‌适用于带非负权重的有向图或无向图无法处理含负权边的图。2核心思想‌采用贪心策略逐步扩展离源点最近的未访问节点更新邻接节点的最短距离。● Dijkstra 算法的堆优化1朴素 Dijkstra 算法每次需遍历所有节点寻找距离起点最近的未访问节点造成大量冗余计算致朴素 Dijkstra 算法的总时间复杂度为 O(n²)。特别的在节点数较多时如 n10⁵性能急剧下降。2而堆优化 Dijkstra 算法通过优先队列小根堆将查找最小距离节点的操作从 O(n) 优化至 O(1)可使堆优化 Dijkstra 算法的总时间复杂度优化为 O(mlogn)m为边数。3堆优化的本质是通过‌小根堆动态维护最小距离节点‌和‌避免全局扫描‌将算法效率从 O(n²) 优化至 O(mlogn)尤其适用于稀疏图或大规模节点场景。● 链式前向星https://blog.csdn.net/hnjzsyjyj/article/details/139369904“链式前向星”就是“多单链表”每条单链表基于“头插法”并用 e[]、ne[]、h[] 、val[] 等数组进行模拟创建。其中e[idx]存储序号为 idx 的边的终点值ne[idx]存储序号为 idx 的边指向的边的序号模拟链表指针‌h[a]存储头结点 a 指向的边的序号val[idx]存储序号为 idx 的边的权值可选● 本题 Dijkstra 算法的两种朴素实现基于链式前向星的实现详见https://blog.csdn.net/hnjzsyjyj/article/details/147467751​​​​​基于邻接矩阵的实现详见https://blog.csdn.net/hnjzsyjyj/article/details/147463593【算法代码】#include bits/stdc.h using namespace std; typedef pairint,int PII; //dis,idx const int inf0x3f3f3f3f; const int N2e55; int h[N],e[N1],ne[N1],val[N1],idx; int st[N],dis[N]; int n,m; void add(int a,int b,int w) { val[idx]w,e[idx]b,ne[idx]h[a],h[a]idx; } int dijkstra() { priority_queuePII,vectorPII,greaterPII q; memset(dis,inf,sizeof dis); dis[1]0; q.push({0,1}); //dis,idx while(!q.empty()) { auto tq.top(); q.pop(); int ut.second; //idx if(st[u]) continue; st[u]true; for(int ih[u]; i!-1; ine[i]) { int je[i]; if(dis[j]dis[u]val[i]) { dis[j]dis[u]val[i]; q.push({dis[j],j}); } } } if(dis[n]inf) return -1; return dis[n]; } int main() { memset(h,-1,sizeof(h)); cinnm; while(m--) { int a,b,c; cinabc; add(a,b,c); } coutdijkstra()endl; return 0; } /* in: 3 3 1 2 2 2 3 1 1 3 4 out: 3 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/147476181https://blog.csdn.net/hnjzsyjyj/article/details/147467751https://blog.csdn.net/hnjzsyjyj/article/details/139369904