企业官网建设流程全解析

网站建设前端岗位职责,大连模板建站软件,知乎 网站开发工具,php网站开发技术描述【题目描述】罗老师被邀请参加一个舞会#xff0c;是在城市n#xff0c;而罗老师当前所处的城市为1,附近还有很多城市2∼n−1#xff0c;有些城市之间没有直接相连的路#xff0c;有些城市之间有直接相连的路#xff0c;这些路都是双向的#xff0c;当然也可能有多条。现…【题目描述】罗老师被邀请参加一个舞会是在城市n而罗老师当前所处的城市为1,附近还有很多城市2∼n−1有些城市之间没有直接相连的路有些城市之间有直接相连的路这些路都是双向的当然也可能有多条。现在给出直接相邻城市的路长度罗老师想知道从城市1到城市n最短多少距离。【输入】输入n, m表示n个城市和m条路;接下来m行每行abc 表示城市a与城市b有长度为c的路。【输出】输出1到n的最短路。如果1到达不了n就输出−1。【输入样例】5 5 1 2 20 2 3 30 3 4 20 4 5 20 1 5 100【输出样例】90【提示】【数据规模和约定】1≤n≤20001≤m≤100000≤c≤100000. 题目速览题意给定N个点M条边的无向正权图求点1到点N的最短距离。不可达输出 -1。数据N2000M10000。1. 核心难点与算法选型做题时首先分析数据量面对N2000的数据选择错误的算法直接导致tle算法复杂度计算量预估判决评价FloydO(N^3)8*10^9必挂只能跑N300。80亿次运算需要几十秒。Bellman-FordO(N*M)4*10^7勉强过效率一般若N再大一点就会超时。SPFAAvg O(k* M)约2*10^5AC平均极快但最坏情况退化为O(N*M)。正权图不建议作为首选。Dijkstra (堆优化)O(M log N)约 2*10^5完美 AC正权图首选最稳定无视数据构造。结论本题最佳方案为Dijkstra堆优化。2. 易错点无向图陷阱题目是双向路存图时必须建两条边addedge(u, v, w)和addedge(v, u, w)。如果是邻接矩阵Floyd记得g[u][v] g[v][u] min(...)。头文件使用memset建议加cstring。使用min/max建议加algorithm。注这是比赛中最常见的 CE 原因。不可达判断初始化dis为INF(如0x3f3f3f3f)。输出前检查if (dis[n] 0x3f3f3f3f) cout -1;。3. 完整代码//n是2*10^3量级此题最佳还是Dijkstra 但我也写个spfa和floyd做个示范 /* //第一种 Dijkstra #include iostream #include queue #include cstring using namespace std; const int maxn2100; const int maxm21000; int n,m; int h[maxn]; int vtex[maxm]; int nxt[maxm]; int wt[maxm]; int idx; int dis[maxn];//每个城市到1号城市到最短距离 int vis[maxn]; struct node{ int id;//每个城市编号 int w;//每个城市到一号城市的最短距离 //优先队列默认大根堆重载运算符变为小根堆 friend bool operator (node a,node b){ return a.wb.w; } }; priority_queuenode q; void dijkstra(int s){ dis[s]0;//起点到自己距离为0 node tmp; tmp.ids; tmp.w0;//记录这个才能确保每次出队都是离1号城市距离最近的城市 q.push(tmp);//源点入队 while(!q.empty()){ tmpq.top();//访问队首元素 q.pop();//队首出队 int nidtmp.id;//当前出队城市编号 if(vis[nid]1) continue;//如果tmp已经出队过就直接跳过 vis[nid]1;//否则就打上出队标记 int ph[nid];//记录tmp头指针 while(p!-1){//遍历tmp所有邻接点 if(vis[vtex[p]]0){//如果该邻接点没有出队过 //如果该邻接点到1号城市距离大于 tmp到1号城市距离边权 //就更新该邻接点到1号城市距离并入队 if(dis[vtex[p]]dis[nid]wt[p]){ dis[vtex[p]]dis[nid]wt[p]; q.push({vtex[p],dis[vtex[p]]}); } } 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(){ cinnm; memset(h,-1,sizeof(h));//初始化头指针数组 //邻接表存图 for(int i1;im;i){ int u,v,w; cinuvw; addedge(u,v,w);//双向道路 addedge(v,u,w); } for(int i1;in;i) dis[i]0x3f3f3f3f;//初始化最短距离为无穷 dijkstra(1); if(dis[n]0x3f3f3f3f) cout-1; else coutdis[n]; return 0; } */ /* //floyd #include iostream #include cstring #include algorithm using namespace std; int n,m; int g[2100][2100]; void floyd(){ for(int k1;kn;k){ for(int i1;in;i){ for(int j1;jn;j){ g[i][j]min(g[i][j],g[i][k]g[k][j]); } } } } int main(){ cinnm; //初始化邻接矩阵内所有城市间距离为无穷 for(int i1;in;i){ for(int j1;jn;j){ g[i][j]0x3f3f3f3f; } } for(int i1;in;i) g[i][i]0;//所有城市自己到自己距离为0 //邻接矩阵存图 for(int i1;im;i){ int u,v,w; cinuvw; //防止两个城市间有多条重复边但是边距离不同 g[u][v]g[v][u]min(g[u][v],w); } floyd(); if(g[1][n]0x3f3f3f3f) cout-1; else coutg[1][n]; return 0; } */ /* //spfa #include iostream #include cstring #include queue using namespace std; queueint q; const int maxn2100; const int maxm21000; int n,m; int h[maxn]; int vtex[maxm]; int nxt[maxm]; int wt[maxm]; int idx; int dis[maxn];//每个城市到1号城市到最短距离 bool is_used[maxn];//记录每个城市是否在队列中 void spfa(int s){ int tmps; dis[tmp]0;//源点到自己距离为0 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){ is_used[vtex[p]]1; q.push(vtex[p]); } } 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(){ cinnm; memset(h,-1,sizeof(h));//初始化头指针数组 //邻接表存图 for(int i1;im;i){ int u,v,w; cinuvw; addedge(u,v,w);//双向道路 addedge(v,u,w); } for(int i1;in;i) dis[i]0x3f3f3f3f;//初始化所有点到dis的距离为无穷 spfa(1); if(dis[n]0x3f3f3f3f) cout-1; else coutdis[n]; return 0; } */ //bellman-ford #include iostream using namespace std; int n,m; struct edge{ int u; int v; int w; }e[21000];//存所有边 int dis[2100]; void ford(int s){ dis[s]0;//起点到自己距离为0 for(int i1;in;i){//迭代n-1次 bool flag0;//标记这一整轮是否发生更新 for(int j1;j2*m;j){//双向道路所以是2*m条 //如果一条边终点到源点距离大于 边起点到源点距离边权 就更新边终点到源点距离 if(dis[e[j].v]dis[e[j].u]e[j].w){ dis[e[j].v]dis[e[j].u]e[j].w; flag1;//并更新标记 } } if(flag0) break;//当一整轮都没有发生更新就退出 } } int main(){ cinnm; for(int i1;in;i) dis[i]0x3f3f3f3f;//初始化每个点到源点距离为0 for(int i1;im;i){ int a,b,c; cinabc; e[i].ue[im].va;//双向边 e[i].ve[im].ub; e[i].we[im].wc; } ford(1); if(dis[n]0x3f3f3f3f) cout-1; else coutdis[n]; return 0; }4. 笔记SPFA vs Bellman-Ford很多同学纠结于负权边算法的选择这里统一总结正权图无脑选Dijkstra。负权图 (无负环)首选SPFA。它是 Bellman-Ford 的队列优化版平均效率高出几十倍。什么时候用 Bellman-Ford题目限制路径最多经过k条边。图极其稠密或特殊构造导致 SPFA 退化严重极罕见。