题意
- 给定(n)个点(m)条边带点权的无向联通图
- A在(s)点，B在(t)点，每人最初的值为0，每人每次可以选择一个距离(d)，将所有与他自己距离不超过(d)的点标记
- 然后将自己的值加上本次所有标记了的点的权值，每次至少标记一个点，直到所有点都标记为止，最后值大的人获胜
博弈论，将每个点到另外两点的距离跑出来，然后扔到坐标系里，发现每次选择相当于将每个人的直线向下/右平移，标记所有未标记的点
考虑记(f_{n, m, 0/1})表示当前可以选(n~N,m~M)点，先手/后手能得到的最大权值，然后从后往前以及从下往上转移就好了
#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 2000
#define maxm 100000
using namespace std;
int n, m, s, t, hd[maxn + 5], len = 0, a[maxn + 5], cnt[2];
LL sum[maxn + 5][maxn + 5], b[2][maxn + 5], ma[maxn + 5][maxn + 5], f[2][maxn + 5][maxn + 5], mx[maxn + 5], now[maxn + 5];
struct Edge{int v, w, net;} e[2 * maxn + 5];
void add(int u, int v, int w){e[len] = (Edge){v, w, hd[u]}; hd[u] = len++;}
LL dis[2][maxn + 5];
void dij(int x, int ty){
memset(dis[ty], inf, sizeof dis[ty]); dis[ty][x] = 0;
priority_queue<pair<LL, int> > q;
q.push(mp(0, x));
while(q.size()){
int u = q.top().sec; q.pop();
Tra(u, i){
int v = e[i].v, w = e[i].w;
if(dis[ty][v] <= dis[ty][u] + w) continue;
dis[ty][v] = dis[ty][u] + w;
q.push(mp(-dis[ty][v], v));
}
}
}
int main(){
//freopen("in", "r", stdin);
memset(hd, -1, sizeof hd);
scanf("%d %d %d %d", &n, &m, &s, &t);
For(i, 1, n) scanf("%d", &a[i]);
For(i, 1, m){
int u, v, w; scanf("%d %d %d", &u, &v, &w);
add(u, v, w); add(v, u, w);
}
dij(s, 0);
For(i, 1, n) b[0][++cnt[0]] = dis[0][i];
sort(b[0] + 1, b[0] + cnt[0] + 1);
cnt[0] = unique(b[0] + 1, b[0] + cnt[0] + 1) - b[0] - 1;
For(i, 1, n) dis[0][i] = lower_bound(b[0] + 1, b[0] + cnt[0] + 1, dis[0][i]) - b[0];
dij(t, 1);
For(i, 1, n) b[1][++cnt[1]] = dis[1][i];
sort(b[1] + 1, b[1] + cnt[1] + 1);
cnt[1] = unique(b[1] + 1, b[1] + cnt[1] + 1) - b[1] - 1;
For(i, 1, n) dis[1][i] = lower_bound(b[1] + 1, b[1] + cnt[1] + 1, dis[1][i]) - b[1];
For(i, 1, n) sum[dis[0][i]][dis[1][i]] += a[i], ma[dis[0][i]][dis[1][i]] = 1;
/*cout << cnt[0] << " " << cnt[1] << endl;
For(i, 1, cnt[0]){
For(j, 1, cnt[1]) cout << sum[i][j] << " ";
cout << endl;
}
cout << endl;*/
Rof(i, cnt[0], 1) Rof(j, cnt[1], 1){
sum[i][j] += sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1];
ma[i][j] += ma[i + 1][j] + ma[i][j + 1] - ma[i + 1][j + 1];
}
For(i, 1, cnt[1]) now[i] = cnt[0], mx[i] = cnt[0] + 1;
Rof(i, cnt[0], 1){
int nowi = cnt[1], mxi = cnt[1] + 1;
Rof(j, cnt[1], 1){
while(now[j] > i && ma[i][j] - ma[now[j]][j]){
if(sum[now[j]][j] - f[1][now[j]][j] + sum[i][j] - sum[now[j]][j] > sum[mx[j]][j] - f[1][mx[j]][j] + sum[i][j] - sum[mx[j]][j]) mx[j] = now[j];
now[j]--;
}
f[0][i][j] = sum[mx[j]][j] - f[1][mx[j]][j] + sum[i][j] - sum[mx[j]][j];
while(nowi > j && ma[i][j] - ma[i][nowi]){
if(sum[i][nowi] - f[0][i][nowi] + sum[i][j] - sum[i][nowi] >= sum[i][mxi] - f[0][i][mxi] + sum[i][j] - sum[i][mxi]) mxi = nowi;
nowi--;
}
f[1][i][j] = sum[i][mxi] - f[0][i][mxi] + sum[i][j] - sum[i][mxi];
}
}
LL tem = f[0][1][1] - (sum[1][1] - f[0][1][1]);
if(tem > 0) puts("Break a heart");
else if(tem < 0) puts("Cry");
else puts("Flowers");
return 0;
}