题目链接:CF536D
首先从 s,t 分别跑一次最短路,容易发现答案仅与其相对大小有关,因此先离散化。
容易将其抽象成一个表格,其中第 i 号点位于 (d_{s,i},d_{t,i}),权值为 p_i,两人分别从 上/左 取若干 行/列。
注意到 n\leq 2\times 10^3,考虑 dp,设 f_{k,i,j} 表示在各自最优策略下当前小 X/小 Y 先手,剩余的点为 (i,j) 及其右下角范围,小 X 的权值与小 Y 的权值的差。
发现其实没必要枚举每个人取到哪一行/列进行转移,只需要一行行一列列转移时注意是否要交给对方即可。
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2e3+10,M=1e5+10;
int n,m,s[2],a[N],vis[N],fir[N],nxt[M<<1],son[M<<1],w[M<<1],tot,cnt,c[2],sz[N][N];
LL sum[N][N],b[N],dp[2][N][N],F[2][N];
I void Add(CI x,CI y,CI z){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y,w[tot]=z;}
#define to son[i]
queue<int> q;
I void Spfa(){
RI u,i,j;for(memset(vis,0,sizeof(vis)),memset(F,63,sizeof(F)),j=0;j<2;j++){
W(!q.empty()) q.pop();F[j][s[j]]=0,q.push(s[j]);W(!q.empty())
for(vis[u=q.front()]=0,q.pop(),i=fir[u];i;i=nxt[i]) F[j][to]>F[j][u]+w[i]&&(F[j][to]=F[j][u]+w[i],!vis[to]&&(q.push(to),vis[to]=1));
}
}
I int Sz(CI i1,CI j1,CI i2,CI j2){return sz[i2][j2]-sz[i1-1][j2]-sz[i2][j1-1]+sz[i1-1][j1-1];}
I LL Sum(CI i1,CI j1,CI i2,CI j2){return sum[i2][j2]-sum[i1-1][j2]-sum[i2][j1-1]+sum[i1-1][j1-1];}
int main(){
RI i,j,k,x,y,z;for(read(n,m,s[0],s[1]),i=1;i<=n;i++) read(a[i]);
for(i=1;i<=m;i++) read(x,y,z),Add(x,y,z),Add(y,x,z);
for(Spfa(),k=0;k<2;k++){
for(cnt=0,i=1;i<=n;i++) b[++cnt]=F[k][i];
for(sort(b+1,b+cnt+1),c[k]=cnt=unique(b+1,b+cnt+1)-b-1,i=1;i<=n;i++) F[k][i]=lower_bound(b+1,b+cnt+1,F[k][i])-b;
}
for(i=1;i<=n;i++) sum[F[0][i]][F[1][i]]+=a[i],sz[F[0][i]][F[1][i]]++;
for(i=1;i<=c[0];i++) for(j=1;j<=c[1];j++) sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1],sz[i][j]+=sz[i-1][j]+sz[i][j-1]-sz[i-1][j-1];
for(i=c[0];i;i--) for(j=c[1];j;j--){
if(Sz(i,j,i,c[1])) dp[0][i][j]=max(dp[0][i+1][j],dp[1][i+1][j])+Sum(i,j,i,c[1]);
else dp[0][i][j]=dp[0][i+1][j];
if(Sz(i,j,c[0],j)) dp[1][i][j]=min(dp[0][i][j+1],dp[1][i][j+1])-Sum(i,j,c[0],j);
else dp[1][i][j]=dp[1][i][j+1];
}
return puts(dp[0][1][1]>0?"Break a heart":dp[0][1][1]<0?"Cry":"Flowers"),0;
}