此题其实比较板,只是我没看出来
首先肯定要跑个最短路,然后发现可以离散化把值域缩小
然后 n n n 很小,直接暴力列个 n 2 n^2 n2 dp。
转移要注意的是必须从大往小dp。从小到大会产生后效性。文章来源:https://uudwc.com/A/ZGDzW
然后拿个双指针优化下转移就行。文章来源地址https://uudwc.com/A/ZGDzW
// LUOGU_RID: 126383363
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 2010
//#define M
//#define mo
struct node {
int y, w;
};
int n, m, i, j, k, T;
priority_queue<pair<int, int> >q;
int sum[N][N], cnt[N][N], s1[N], s2[N], f[N][N][2], x, y, u, v, w;
int z[N], vis[N], val[N], st, ed, mn, mn1[N], mn2[N], o1[N], o2[N];
vector<node>G[N];
void dij(int s, int ans[N]) {
for(i=1; i<=n; ++i) ans[i]=1e18;
q.push({0, s}); ans[s]=0;
while(!q.empty()) {
u=q.top().second; q.pop();
for(auto t : G[u]) {
v=t.y;
// printf("%d -> ")
if(ans[u]+t.w<ans[v]) {
ans[v]=ans[u]+t.w;
q.push({ans[v], v});
}
}
}
for(i=1; i<=n; ++i) z[i]=ans[i];
// for(i=1; i<=n; ++i) printf("%lld ", ans[i]); printf("\n");
sort(z+1, z+n+1);
for(i=1; i<=n; ++i) ans[i]=lower_bound(z+1, z+n+1, ans[i])-z;
}
void calc(int sum[N][N]) {
for(i=0; i<=n; ++i) {
for(j=1; j<=n; ++j) vis[j]=0;
for(j=1; j<=n; ++j)
if(s1[j]<=i) vis[j]=1, sum[i][0]+=val[j];
for(j=1; j<=n; ++j) if(!vis[j]) sum[i][s2[j]]+=val[j];
for(j=1; j<=n; ++j) sum[i][j]+=sum[i][j-1];
}
int num=sum[n][n];
for(i=0; i<=n; ++i) for(j=0; j<=n; ++j) sum[i][j]=num-sum[i][j];
}
signed main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// T=read();
// while(T--) {
//
// }
n=read(); m=read(); st=read(); ed=read();
for(i=1; i<=n; ++i) val[i]=read();
for(i=1; i<=m; ++i) {
u=read(); v=read(); w=read();
G[u].pb({v, w}); G[v].pb({u, w});
}
k=0; dij(st, s1); dij(ed, s2);
// for(i=1; i<=n; ++i) printf("%lld ", s1[i]); printf("\n");
// for(i=1; i<=n; ++i) printf("%lld ", s2[i]); printf("\n");
calc(sum); fill(val+1, val+n+1, 1); calc(cnt);
memset(f, 0x80, sizeof(f));
for(i=0; i<=n; ++i)
o1[i]=o2[i]=n, mn1[i]=mn2[i]=1e18;
for(i=n; i>=0; --i)
for(j=n; j>=0; --j) {
if(cnt[i][j]==0) {
f[i][j][0]=f[i][j][1]=0; continue;
}
for(int &k=o1[j]; k>i && cnt[k][j]<cnt[i][j]; --k)
mn1[j]=min(mn1[j], f[k][j][1]);
f[i][j][0]=sum[i][j]-mn1[j];
for(int &k=o2[i]; k>j && cnt[i][k]<cnt[i][j]; --k)
mn2[i]=min(mn2[i], f[i][k][0]);
f[i][j][1]=sum[i][j]-mn2[i];
// for(k=n, mn=1e18; k>i && cnt[k][j]<cnt[i][j]; --k)
// f[i][j][0]=max(f[i][j][0], sum[i][j]-f[k][j][1]);
// for(k=n, mn=1e18; k>j && cnt[i][k]<cnt[i][j]; --k)
// f[i][j][1]=max(f[i][j][1], sum[i][j]-f[i][k][0]);
// printf("f[%lld][%lld][0/1]=%lld %lld | %lld %lld %lld %lld\n", i, j, f[i][j][0], f[i][j][1], sum[i][j], mn, cnt[i][j], cnt[2][j]);
}
x=f[0][0][0], y=sum[0][0]-x;
// printf("%lld | %lld %lld\n", sum[0][0], x, y);
if(x>y) printf("Break a heart");
else if(y>x) printf("Cry");
else printf("Flowers");
return 0;
}