codeforces 704B - Ant Man 贪心

时间：2024-01-15 19:06:08
 codeforces 704B - Ant Man 贪心

 题意：n个点，每个点有5个值，每次从一个点跳到另一个点，向左跳：abs(b.x-a.x)+a.ll+b.rr

 向右跳：abs(b.x-a.x)+a.lr+b.rl，遍历完所有的点，问你最后的花费是多少

 思路：每次选一个点的时候，在当前确定的每个点比较一下，选最短的距离。

 为什么可以贪心？应为答案唯一，那么路径必定是唯一的，每个点所在的位置也一定是最短的。

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 const int inf = 0x3f3f3f3f;

 const int MOD =;

 const int N =;

 #define clc(a,b) memset(a,b,sizeof(a))

 const double eps = 1e-;

 void fre() {freopen("in.txt","r",stdin);}

 void freout() {freopen("out.txt","w",stdout);}

 inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-;ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;}

 struct node{

     LL x;

     LL rl,rr,ll,lr;

 }p[];

 LL fun(node a,node b){

     if(b.x<a.x) return abs(b.x-a.x)+a.ll+b.rr;

     return abs(b.x-a.x)+a.lr+b.rl;

 }

 LL net[];

 int  main(){

     int n,a,b;

     scanf("%d%d%d",&n,&a,&b);

     for(int i=;i<=n;i++) scanf("%I64d",&p[i].x);

     for(int i=;i<=n;i++) scanf("%I64d",&p[i].rl);

     for(int i=;i<=n;i++) scanf("%I64d",&p[i].rr);

     for(int i=;i<=n;i++) scanf("%I64d",&p[i].ll);

     for(int i=;i<=n;i++) scanf("%I64d",&p[i].lr);

     LL tem,sum,ans=;

     int k;

     net[a]=b;

     ans+=fun(p[a],p[b]);

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

         if(i==a||i==b) continue;

         sum=1e18;

         for(int j=a;j!=b;j=net[j]){

             tem=fun(p[j],p[i])+fun(p[i],p[net[j]])-fun(p[j],p[net[j]]);

             if(tem<sum){

                 sum=tem;

                 k=j;

             }

         }

         ans+=sum;

         net[i]=net[k];

         net[k]=i;

     }

     printf("%I64d\n",ans);

     return ;

 }

相关文章