题解 P4779 【【模板】单源最短路径（标准版）】

~~求大佬勿喷~~ 堆优化Dijkstra算法别的大佬应该已经介绍得很详细了，但是都是用stl的模板的。本蒻在这里贴一下自己的手打堆。虽然手打堆确实很沙逼，但是stl模板库自带的堆是用vector实现的，常数要大一点。而手打的堆是很快的。从程序效率的角度看是手打堆更好，但是从编程复杂度和调试难度的角度看，在比赛时往往很缺时间，一般能用模板的尽量用模板吧。 ** ~~会用stl还不会手打堆？~~ ** ```cpp #include<cstdio> #include<cctype> #define maxn 100005 #define maxm 500005 using namespace std; const int INF=0x7fffffff; struct edge{ int to,len,next; }a[maxm];//邻接表 int size; int n,m,s; int head[maxn]; inline void addedge(int from,int to,int len) { a[++size].next=head[from]; a[size].len=len; a[size].to=to; head[from]=size; } int dis[maxn]; int b[maxn]; //手打堆 struct b_heap{ int v,i; }h[maxn]; int heap_size; inline void hswap(b_heap &a,b_heap &b) { a.v^=b.v^=a.v^=b.v; a.i^=b.i^=a.i^=b.i; } inline int redi() { register int ret=0;register char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)){ret=ret*10+ch-48;ch=getchar();} return ret; } inline void put(int v,int i) { h[++heap_size].v=v; h[heap_size].i=i; int np=heap_size; while(np>1&&h[np].v<h[np>>1].v) { hswap(h[np],h[np>>1]); np>>=1; } } inline int get() { // if(heap_size==0)return 0; int ret=h[1].i;int np=1,ind; h[1].v=h[heap_size].v; h[1].i=h[heap_size].i; --heap_size; while((np<<1)<=heap_size) { ind=np<<1; if(h[ind].v>h[ind+1].v) ++ind; if(h[np].v<h[ind].v) break; hswap(h[np],h[ind]); np=ind; } return ret; } int main() { register int t1,t2,t3,i,j; // scanf("%d%d%d",&n,&m,&s); n=redi();m=redi();s=redi(); for(i=1;i<=m;++i) { // scanf("%d%d%d",&t1,&t2,&t3); t1=redi();t2=redi();t3=redi(); addedge(t1,t2,t3); // addedge(t2,t1,t3); } for(i=1;i<=n;++i) { dis[i]=INF; } dis[s]=0; put(0,s); while(heap_size) { int index=0; index=get(); if(!index)break; if(b[index])continue; b[index]=1; for(j=head[index];j;j=a[j].next) { if(dis[index]+a[j].len<dis[a[j].to]) { dis[a[j].to]=dis[index]+a[j].len; put(dis[a[j].to],a[j].to); } } } for(i=1;i<=n;++i) { printf("%d ",dis[i]); } // printf("%lld",dis[t]); return 0; } ``` 附stl模板库版本： ```cpp #include<cstdio> #include<cctype> #include<queue> #define maxn 100005 #define maxm 500005 #define rs register using namespace std; const int INF=0x7fffffff; int n,m,s; // struct cmp{ bool operator() (pair<int,int>a,pair<int,int>b) { return a.first<b.first; } };//伪函数 struct edge{ int to,len,next; }a[maxm]; int a_size; int head[maxn]; inline void addedge(int from,int to,int len) { a[++a_size].next=head[from]; a[a_size].len=len; a[a_size].to=to; head[from]=a_size; } //heap //priority_queue<pair<int,int>,vector<pair<int,int> >,cmp>h; priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >h; //heap e int dis[maxn]; int b[maxn]; template <typename T> inline void redi(T& t) { int f=0,c=getchar();t=0; while(!isdigit(c))/*f|=c=='-',*/c=getchar(); while(isdigit(c))t=t*10+c-48,c=getchar(); // if(f)t=-t; } template <typename T, typename... Args> inline void redi(T& t, Args&... args) { redi(t);redi(args...); }//读优模板，抄大佬的。这么写看起来高级一点233 void dijkstra(int si) { for(rs int i=1;i<=n;++i)dis[i]=INF; dis[si]=0; h.push(make_pair(0,si)); // memset(b,0,sizeof(b)); while(h.size()) { rs int t=h.top().second;h.pop(); if(b[t]) continue; b[t]=1; for(rs int i=head[t];i;i=a[i].next) { rs int t1=a[i].len,t2=a[i].to; if(dis[t2]>dis[t]+t1) { dis[t2]=dis[t]+t1; h.push(make_pair(dis[t2],t2)); } } } } int main() { rs int t1,t2,t3; redi(n,m,s); for(rs int i=1;i<=m;++i) { redi(t1,t2,t3); addedge(t1,t2,t3); } dijkstra(s); for(rs int i=1;i<=n;++i) { printf("%d ",dis[i]); } return 0; } ``` [手打堆提交记录](https://www.luogu.org/record/show?rid=12306031) [stl模板堆提交记录](https://www.luogu.org/record/show?rid=12289498) 笔者不是来秀代码的，况且dalao的代码可以碾压我。我只是介绍一种思路。可以看到手打堆的效率差不多是stl自带的三倍，在时间宽裕的情况下还是值得选择的。说不定几个原来T掉的点就过了呢。~~一般没有这种情况的~~