洛谷原題

這題我自己看了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] 【模板】单源最短路径（标准版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。