[USACO14DEC]驮运Piggy Back

题目描述

Bessie 和 Elsie在不同的区域放牧，他们希望花费最小的能量返回谷仓。从一个区域走到一个相连区域，Bessie要花费B单位的能量，Elsie要花费E单位的能量。

如果某次他们两走到同一个区域，Bessie 可以背着 Elsie走路，花费P单位的能量走到另外一个相连的区域，满足P<B+E。

相遇后，他们可以一直背着走，也可以独立分开。

输入输出样例

输入样例#1：

输出样例#1：

22 
3次SPFA就可以了
可以知道，他们在相遇后就不分开了，因为背到终点一定最优
dist1[x]表示从1出发到x最短路
dist2同理
dist3表示到n的最短路
ans=min(dist1[x]*b+dist2[x]*e+dist3[x]*p)

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 struct Messi

 {

     int next,to;

 }edge[];

 int head[],num,n,m,f[][],ans,dist[],vis[];

 void add(int u,int v)

 {

     num++;

     edge[num].next=head[u];

      head[u]=num;

      edge[num].to=v;

 }

 void bfs(int x)

 {int q[]={},h,t,u,v,i;

     q[]=x;h=;t=;

      while (h<t)

      {

          h++;

           u=q[h];

           vis[u]=;

            for (i=head[u];i;i=edge[i].next)

            {

                int v=edge[i].to;

                 if (dist[u]+<dist[v])

                 {

                     dist[v]=dist[u]+;

                     if (vis[v]==)

                      t++,q[t]=v;

              }

            }

      }

 //     cout<<x<<' ';

 //    for (i=1;i<=n;i++)

 //    cout<<dist[i]<<' ';

 //    cout<<endl;

 }

 int main()

 {int b,e,p,i,u,v;

     cin>>b>>e>>p>>n>>m;

      for (i=;i<=m;i++)

       {

           scanf("%d%d",&u,&v);

           add(u,v);

           add(v,u);

       }

       memset(dist,/,sizeof(dist));dist[]=;memset(vis,,sizeof(vis));

      bfs();

       for (i=;i<=n;i++)

         f[i][]=dist[i];

        memset(dist,/,sizeof(dist));dist[]=;memset(vis,,sizeof(vis));

      bfs();

      for (i=;i<=n;i++)

         f[i][]=dist[i];

      memset(dist,/,sizeof(dist));dist[n]=;memset(vis,,sizeof(vis));

      bfs(n);

      for (i=;i<=n;i++)

         f[i][]=dist[i];

     ans=2e9;

     for (i=;i<=n;i++)

      ans=min(ans,f[i][]*b+f[i][]*e+f[i][]*p);

      cout<<ans;

 }

巴特西

[USACO14DEC]驮运Piggy Back

题目描述

输入输出样例

最新文章

热门文章