[最短路/线段树大法优化DIJ] 【模板】单源最短路径（标准版）

洛谷原题

这题我自己看了STL优先队列后试了试优化DIJ算法，但我这个菜比只有32分...

还是老老实实用线段树吧！

自己写的程序，反正AC了，线段树大法好！

具体见代码

#include<bits/stdc++.h> using namespace std; long long dis[800005],v[400005],ans[400005]; int num[800005]; int dian,gai,ans1;//dian是点的标号，用于查询与修改；gai是要修改的值，用于修改；ans1是查询dian到原点的距离 int n,m,s=1; bool u[400005]; int first[400005],next[400005],b[400005]; void biu(int t,int l,int r) {dis[t]=2100000005;if(l==r) {num[t]=l;return;}int mid=l+r>>1;biu(2*t,l,mid);biu(2*t+1,mid+1,r);num[t]=num[2*t]; return; } void cha(int t,int l,int r) {if(l==r){dis[t]=gai;return;}int mid=l+r>>1;if(dian<=mid) cha(2*t,l,mid);else cha(2*t+1,mid+1,r);if(dis[2*t]<dis[2*t+1]) {dis[t]=dis[2*t];num[t]=num[2*t];}else {dis[t]=dis[2*t+1];num[t]=num[2*t+1];}return; } void ask(int t,int l,int r) {if(l==r){ans1=dis[t];return;}int mid=l+r>>1;if(dian<=mid) ask(2*t,l,mid);else ask(2*t+1,mid+1,r);return; } int main() {scanf("%d%d",&n,&m);scanf("%d",&s);int xx,yy,zz;for(int i=1;i<=m;i++)//邻接表存图 {scanf("%d%d%d",&xx,&yy,&zz);next[i]=first[xx];first[xx]=i;b[i]=yy;v[i]=zz;}dian=s,gai=0;biu(1,1,n);//建树，所有节点初始为无穷大，线段树维护最小值和对应点标号 cha(1,1,n);//插入第一个点即起点 for(int i=1;i<=n;i++){int k=first[num[1]],fa=num[1];//fa记录当前最小点的标号，处理完后最后将其到原点距离设为无穷大 long long ss=dis[1];ans[num[1]]=ss;u[num[1]]=1;//标记该点已确定，无需更新 while(k){dian=b[k];if(u[b[k]]){k=next[k];continue;}ask(1,1,n);//查询dian到原点的距离ans1， if(ans1>ss+v[k]){gai=ss+v[k];cha(1,1,n);//将dian到原点的距离更新 }k=next[k];}gai=2100000005;dian=fa;//将fa的值修改为无穷大 cha(1,1,n);}for(int i=1;i<=n;i++){printf("%lld ",ans[i]);}//printf("%lld",ans[n]);//输出答案，线段树大法好 return 0; }

 

转载于:https://www.cnblogs.com/Miniweasel/p/9899234.html

总结

以上是生活随笔为你收集整理的[最短路/线段树大法优化DIJ] 【模板】单源最短路径（标准版）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。