题解 P1339 【[USACO09OCT]热浪Heat Wave】

# 前言 实际上这道题就是一道单源最短路径的题目，当然还是有很多方法的，就比如SPFA,dijkstra(标准，堆优化)等等，然而当我看到dalao线段树的题解的时候，只剩下了Orz，现在就来讲一下我的思路吧！ --- # 思路 这次我依然不走寻常路，用的是dijkstra+zkw线段树优化，这份代码是这周日写的，所以说还是比较神奇的,主要思想就是维护最小值，然而我的思路是这样的，首先先在叶子节点处更新dis的最小值以及dis最小值的位置，具体可以表现在 时间复杂度大概是$O(n)$的，然后删除该点的时候需要单点修改，在松弛操作完成后还要进行修改，总的来说时间复杂度是$O(n+elogn)$ --- # 代码(25ms不加O2)(还是比较慢的) ```cpp #include <cstdio> #include <cctype> #include <algorithm> #define rr register using namespace std; const int inf=707406378; struct node{int y,w,next;}e[12501]; int n,m,s,t,bas=1,k=1,ls[2511],w[8201],p[8201],dis[2511]; inline signed iut(){ rr int ans=0; rr char c=getchar(); while (!isdigit(c)) c=getchar(); while (isdigit(c)) ans=(ans<<3)+(ans<<1)+c-48,c=getchar(); return ans; } inline void add(int x,int y,int w){e[++k]=(node){y,w,ls[x]}; ls[x]=k;} inline void update(int x){ w[x]=(w[x<<1]<w[x<<1|1])?w[x<<1]:w[x<<1|1];//取左子右子最小值 p[x]=(w[x<<1]>w[x<<1|1])?p[x<<1|1]:p[x<<1];//实时更新编号 } signed main(){ n=iut(); m=iut(); s=iut(); t=iut(); for (rr int i=1;i<=m;++i){ rr int x=iut(),y=iut(),w=iut(); add(x,y,w); add(y,x,w); } while ((bas<<=1)<n+2);//由于区间修改需要扩张，所以实际上空间要多1位，总之应在2^x>n的范围内 fill(w+1,w+2+(bas<<1),inf); fill(dis+1,dis+1+n,inf);//全部初始话位一个很大的值 fill(p+1,p+2+(bas<<1),inf); w[s+bas-1]=dis[s]=0;//那么 for (rr int i=0;i<n;++i) p[bas+i]=i+1;//输入编号 for (rr int i=bas-1;i;--i) update(i);//记住bas表示的是当为满二叉树时除最后一层的个数+1，所以说要减掉1 while (w[1]<inf){//也就是说都没有访问过 rr int x=p[1],y=p[1]+bas-1; w[y]=inf; for (y>>=1;y;y>>=1) update(y);//删除现在的最小点 for (rr int i=ls[x];i;i=e[i].next) if (dis[e[i].y]>dis[x]+e[i].w){//这一段长的挺像SPFA的 dis[e[i].y]=dis[x]+e[i].w; rr int t=e[i].y+bas-1; for (w[t]=dis[e[i].y],t>>=1;t;t>>=1) update(t);//松弛操作后新到达的节点插入zkw线段树中 } } return !printf("%d",dis[t]);//输出s到t的距离 } ```