首页 > 代码库 > 【POJ3377】Ferry Lanes 最短路
【POJ3377】Ferry Lanes 最短路
我只是贴一下手写堆优化的dij模板,虽然,它,TLE了……****
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 2001000 #define inf 0x3f3f3f3f #define longlong int using namespace std; struct Katarina { int v,next; longlong len; }e[N<<2]; int head[N],cnt; void add(int u,int v,longlong len) { cnt++; e[cnt].v=v; e[cnt].len=len; e[cnt].next=head[u]; head[u]=cnt; } struct Fiona { longlong f; int v; bool operator < (const Fiona &a)const {return f<a.f;} bool operator >= (const Fiona &a)const {return f>=a.f;} bool operator > (const Fiona &a)const {return f>a.f;} Fiona(longlong _f,int _v):f(_f),v(_v){} Fiona(){} }; struct Heap { Fiona w[N]; int cnt,crs[N]; void init(){cnt=0;memset(crs,0,sizeof(crs));} void pushup(int &x){while((x>>1)&&w[x>>1]>w[x])swap(w[x>>1],w[x]),crs[w[x].v]=x,x>>=1;} void pushdown(int &x) { while((x<<1)<=cnt) { int son=(x<<1==cnt)?(x<<1):(w[x<<1]<w[x<<1|1]?(x<<1):(x<<1|1)); if(w[son]>=w[x])break; else swap(w[x],w[son]),crs[w[x].v]=x; x=son; } } void push(Fiona X) { if(!crs[X.v]) { w[++cnt]=X; pushup(crs[X.v]=cnt); } else { w[crs[X.v]]=X; pushup(crs[X.v]); } } Fiona top()/*add to a pop*/ { Fiona ret=w[1]; crs[w[1].v]=0; w[1]=w[cnt--]; if(cnt)pushdown(crs[w[1].v]=1); return ret; } }heap; longlong dist[N]; bool visit[N]; int n; longlong dij(int s,int t) { int i,u,v,round; heap.init(); memset(dist,0x3f,sizeof(dist)); memset(visit,0,sizeof(visit)); dist[s]=0; heap.push(Fiona(dist[s],s)); for(round=1;round<=n;round++) { Fiona U=heap.top(); u=U.v; visit[u]=1; for(i=head[u];i;i=e[i].next) { v=e[i].v; if(!visit[v]&&dist[v]>dist[u]+e[i].len) { dist[v]=dist[u]+e[i].len; heap.push(Fiona(dist[v],v)); } } } return dist[t]; } int main() { // freopen("test.in","r",stdin); // freopen("1.out","w",stdout); int i,a,b,c,d; int s,t,temp; while(scanf("%d",&n),n) { n++;cnt=0; memset(head,0,sizeof(head)); scanf("%d%d%d%d",&a,&b,&c,&d); s=a*n+b+1; t=c*n+d+1; for(i=1;i<n;i++) { scanf("%d",&temp); add(i,i+1,temp); add(i+1,i,temp); } for(i=1;i<=n;i++) { scanf("%d",&temp); add(i,i+n,temp); add(i+n,i,temp); } for(i=n+1,n<<=1;i<n;i++) { scanf("%d",&temp); add(i,i+1,temp); add(i+1,i,temp); } cout<<dij(s,t)<<endl; } // fclose(stdin); // fclose(stdout); return 0; }
【POJ3377】Ferry Lanes 最短路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。