企业官网建设流程全解析

像优酷这样的网站需要怎么做,外贸平台是什么意思,湖北建设网站四库一平台,wordpress新建404页面【题目描述】给定 M 条边#xff0c; N 个点的带权无向图。求 1到 N 的最短路。【输入】第一行#xff1a;N,M(N100000#xff0c;M500000)#xff1b;接下来M行3个正整数#xff1a;ai,bi,ci表示ai,bi之间有一条长度为ci的路#xff0c;ci1000。【输出】一个…【题目描述】给定 M 条边 N 个点的带权无向图。求 1到 N 的最短路。【输入】第一行N,M(N100000M500000)接下来M行3个正整数ai,bi,ci表示ai,bi之间有一条长度为ci的路ci1000。【输出】一个整数表示 1 到 N 的最短距离。【输入样例】4 4 1 2 1 2 3 1 3 4 1 2 4 1【输出样例】2【提示】【样例解释】注意图中可能有重边和自环,数据保证 1 到 N 有路径相连。0. 题目概要给定N个点 (N10^5) 和M条边 (M5*10^5) 的带权无向图。求从点 1 到点N的最短距离。提示虽然题目指定用 SPFA但在实际工程或比赛中对于正权图堆优化 Dijkstra 是更稳定的选择。1. 算法解析1.1 SPFA 的核心逻辑SPFA是 Bellman-Ford 的队列优化版。核心思想只有“变短了”的点才有可能去更新它的邻居。实现机制用队列维护所有“距离被更新且尚未处理”的节点。取出队首节点u取消标记。遍历u的所有出边 (u, v, w)。松弛操作如果dis[v] dis[u] w则更新dis[v]。如果v更新了且不在队列中将v入队并标记。1.2 空间与时间空间由于是无向图存图时需要建双向边因此边数组的大小必须开到2*M。本题 M500,000数组至少要开1,000,000。时间SPFA 的平均时间复杂度是O(kM)(k为常数约 2~4)。但在最坏情况下如网格图会退化为O(NM)。本题数据通常较弱SPFA 可过。2. 易错点数组越界这是无向图最短路最容易挂的地方M是 50 万vtex,nxt,wt必须开到100 万以上。IO 瓶颈M很大输入数据多建议使用快读或关闭同步流ios::sync_with_stdio(false; cin.tie(0);重边与自环SPFA 的松弛操作if(dis[v] dis[u] w)天然能处理重边会自动选短的那条和自环不会死循环无需特殊处理。3. 完整代码//题目写了spfa 我们就spfa #include iostream #include cstring #include queue using namespace std; int n,m; const int maxn100010; const int maxm1100000; int h[maxn]; int vtex[maxm]; int nxt[maxm]; int wt[maxm]; int idx; int dis[maxn]; int is_used[maxn];//标记每个点是否在队列中 queueint q; void spfa(int s){ dis[s]0;//起点到自己距离为0 int tmps; q.push(tmp);//起点入队 is_used[tmp]1;//打上标记 while(!q.empty()){ tmpq.front();//访问队首 q.pop();//出队 is_used[tmp]0;//取消标记 int ph[tmp];//tmp头指针 while(p!-1){//遍历tmp所有邻接点 //如果该邻接点到源点距离大于 tmp到源点距离边权 if(dis[vtex[p]]dis[tmp]wt[p]){ //就更新该邻接点到源点距离 dis[vtex[p]]dis[tmp]wt[p]; //如果该邻接点不在队中就入队并打上标记否则不用理会 if(is_used[vtex[p]]0){ q.push(vtex[p]); is_used[vtex[p]]1; } } pnxt[p];//更新指针 } } } void addedge(int u,int v,int w){ vtex[idx]v; nxt[idx]h[u]; wt[idx]w; h[u]idx; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; memset(h,-1,sizeof(h)); //邻接表存图 for(int i1;im;i){ int a,b,c; cinabc; addedge(a,b,c);//无向即双向路 addedge(b,a,c); } memset(dis,0x3f,sizeof(dis));//初始化所有点到1距离为无穷 spfa(1); coutdis[n]; return 0; }4. 总结这道题是 SPFA 的入门模板题。优点代码比堆优化 Dijkstra 短逻辑简单能处理负权边。缺点极其不稳定容易被出题人卡tle。策略如果题目没明确说“可能有负权边”尽量首选 Dijkstra。但本题指名道姓要 SPFA那就用数组开够即可。