锐客网

  1. 首页 > 睿知 > it技术 > >

bzoj 2100: [Usaco2010 Dec]Apple Deliveryspfa

IT知识appleUSACOdelivery

【bzoj 2100: [Usaco2010 Dec]Apple Deliveryspfa】生也有涯，知也无涯。这篇文章主要讲述bzoj 2100: [Usaco2010 Dec]Apple Deliveryspfa相关的知识，希望能为你提供帮助。
洛谷数据好强啊，普通spfa开o2都过不了，要加双端队列优化
因为是双向边，所以dis(u,v)=dis(v,u)，所以分别以pa1和pa2为起点spfa一遍，表示pb--> pa1--> pa2和pb--> pa2--> pa1，取个min即可

#include< iostream> #include< cstdio> #include< queue> using namespace std; const int N=200005,inf=2e9+7; int m,n,a,b1,b2,h[N],cnt,dis[N]; bool v[N]; struct qwe { int ne,to,va; }e[N< < 2]; int read() { int r=0,f=1; char p=getchar(); while(p> ‘9‘||p< ‘0‘) { if(p==‘-‘) f=-1; p=getchar(); } while(p> =‘0‘& & p< =‘9‘) { r=r*10+p-48; p=getchar(); } return r*f; } void add(int u,int v,int w) { cnt++; e[cnt].ne=h[u]; e[cnt].to=v; e[cnt].va=w; h[u]=cnt; } void spfa(int s) { deque< int> q; for(int i=1; i< =n; i++) dis[i]=inf; dis[s]=0,v[s]=1,q.push_back(s); while(!q.empty()) { int u=q.front(); q.pop_front(); v[u]=0; for(int i=h[u]; i; i=e[i].ne) if(dis[e[i].to]> dis[u]+e[i].va) { dis[e[i].to]=dis[u]+e[i].va; if(!v[e[i].to]) { v[e[i].to]=1; if(!q.empty()& & dis[q.front()]> dis[e[i].to]) q.push_front(e[i].to); else q.push_back(e[i].to); } } } } int main() { m=read(),n=read(),a=read(),b1=read(),b2=read(); for(int i=1; i< =m; i++) { int x=read(),y=read(),z=read(); add(x,y,z),add(y,x,z); } spfa(b1); int ans=dis[a]+dis[b2]; spfa(b2); printf("%d\n",min(ans,dis[a]+dis[b1])); return 0; }



    推荐阅读


    上一篇：Filtering Approaches for Real-Time Anti-Aliasing（2011 SIGGRAPH）

    下一篇：在fragment中实现Android上传图片至本地JavaWeb服务器