题解 P3110 【[USACO14DEC]驮运Piggy Back】

基地A_I · 2019-04-05 11:14:26 · 题解

题解：P3110 驮运Piggy Back

题目大意：

• 给出一个无向图，Bessie从1号仓库走到n号（每次花费B）， Elsie从2号仓库走到n号（每次花费E），如果两个人走同一条路花费P，求总花费最小。

• 输入B，E，P，n，m和m条边的联通情况

• 输出最少花费。

  题目分析：

• （dalao跳过）我刚开始看到这个题目的时候，确实无法动笔。于是我抱着学(jie)习(jian)的心态打开了题解，发现题解里的大佬都在说什么3个SPFA，3个Dijkstra，跑三遍最短路等等。经过一番思索后，我终于明白了他的意思，所以在这里给还没有弄懂的同学解释一下。

  解题方法

• 先跑三遍最短路（SPFA或者是Dijkstra 当然如果你是大佬Bfs也可以），分别得到Bessie从①出发的最短路,Elsie从②出发的最短路,和从n出发到其他每个点的最短路。最后枚举所以的点

  ans = max(ans ,B*disB[i]+E*disE[i]+P*disP[i]);

• 解释：这个式子代表走着条路的花费，分别是Bessie到i点的距离+Elsie到i点的距离+B&&E到n点的花费。

最后

• 感谢 题解dalao @ezoixx♂130 提供思路（这个名字有点哲学啊）

• 祝你AC（其实这道题还是蛮水的）

• 具体代码如下（温馨提示：不要抄袭）：

  #include<algorithm>
  #include<iostream>
  #include<string.h>
  #include<cstdio>
  #include<cmath>
  #include<queue>
  #define N 100007
  using namespace std;
  int B,P,E,n,m,cnt,ans;   
  int head[N],disB[N],disP[N],disE[N];
  struct Edge
  {
  int next,to;    //边没有权值 
  }edge[N];   //链式前向星存图 
  void add(int u,int v)   //增加边 
  {
  edge[++cnt].next = head[u];
  edge[cnt].to = v;
  head[u] = cnt;
  }
  //  一个朴素的SPFA（QWQ） ，传入s源点，和dis数组（最短路数组） 
  void SPFA(int s,int dis[])   
  {
  //  int num[N];     //无负环
  queue<int> q;
  bool vis[N];
  for(int i=1;i<=n;++i) dis[i] = 88888888;
  //  printf("BiG TesT : dis=%d",dis[5]);
  memset(vis,0,sizeof(vis));
  q.push(s) ,vis[s] = 1 ,dis[s] = 0;
  while(!q.empty())
  {
      int cur = q.front();
      q.pop() ,vis[cur] = 0;
      for(int i=head[cur];i;i=edge[i].next)
      {
          int v = edge[i].to ,w=1;    //权值设置为1 
          if(dis[v] > dis[cur]+w)
          {
              dis[v] = dis[cur]+w;
              if(!vis[v]) vis[v] = 1 ,q.push(v);
          }
      }
  }
  while(1) cout << "Plagiarists are shameless" << endl;
  //  请大家自行翻译一下QWQ 
  }
  int main()
  {
  //  printf("%d",ans);
  scanf("%d%d%d%d%d",&B,&E,&P,&n,&m);
  for(int i=1,u,v;i<=m;++i)
      scanf("%d%d",&u,&v) ,add(u,v) ,add(v,u);
  //  以上输入不用解释吧？ 
  SPFA(1,disB);   //搜B 
  SPFA(2,disE);   //搜E 
  SPFA(n,disP);   //从n开始搜的P 
  //  打擂台 
  ans = 0xfffffff;
  for(int i=1;i<=n;++i)
      ans = min(ans ,B*disB[i]+E*disE[i]+P*disP[i]);
  printf("%d",ans);
  return 0;   //完美结束 
  }

  求管理大大批过 QWQ ！