首页 > 代码库 > bzoj3891[Usaco2014 Dec]Piggy Back*
bzoj3891[Usaco2014 Dec]Piggy Back*
bzoj3891[Usaco2014 Dec]Piggy Back
题意：
给定一个N个点M条边的无向图，其中Bessie在1号点，Elsie在2号点，它们的目的地为N号点。Bessie每经过一条边需要消耗B点能量，Elsie每经过一条边需要消耗E点能量。当它们相遇时，它们可以一起行走，此时它们每经过一条边需要消耗P点能量。求它们两个到达N号点时最少消耗多少能量。n，m≤40000。
题解：
先求出以1、2、n为源点的最短路（因为边权为1所以用bfs）。答案初始设为1到n的最短路*B+2到n的最短路*E。接着枚举每个点，让该点到1最短路*B+该点到2最短路*E+该点到n的最短路*P和答案比较。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 40010 7 using namespace std; 8 9 inline int read(){10 char ch=getchar(); int f=1,x=0;11 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}12 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();13 return f*x;14 }15 struct e{int t,n;}es[maxn*2]; int ess,g[maxn];16 void pe(int f,int t){17 es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;18 }19 int n,m,b,e,p,d[3][maxn]; long long ans; queue<int>q; bool vis[maxn];20 void bfs(int s,int o){21 while(!q.empty())q.pop(); memset(vis,0,sizeof(vis));22 q.push(s); vis[s]=1; d[o][s]=0;23 while(!q.empty()){24 int x=q.front(); q.pop();25 for(int i=g[x];i;i=es[i].n)if(!vis[es[i].t]){26 d[o][es[i].t]=d[o][x]+1; q.push(es[i].t); vis[es[i].t]=1;27 }28 }29 }30 int main(){31 b=read(); e=read(); p=read(); n=read(); m=read(); inc(i,1,m){int x=read(),y=read(); pe(x,y);}32 bfs(1,0); bfs(2,1); bfs(n,2); ans=1LL*d[0][n]*b+1LL*d[1][n]*e;33 inc(i,1,n)if(1LL*d[0][i]*b+1LL*d[1][i]*e+1LL*d[2][i]*p<ans)ans=1LL*d[0][i]*b+1LL*d[1][i]*e+1LL*d[2][i]*p;34 printf("%lld",ans); return 0;35 }
20160909
bzoj3891[Usaco2014 Dec]Piggy Back*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。