日记详情

题目链接：P11927 [PA 2025] 重金属 / Heavy Metal

观察到 $ n $ 特别小以至于 $ O(nsqrt(V)) $ 也能过，考虑根号分治值域 meet in middle，做完了。

代码：

#include<bits/stdc++.h>
#define time(null) chrono::steady_clock::now().time_since_epoch().count()
#define int long long
#define uint unsigned long long
#define debug() cout<<"come here\n"
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pb push_back
#define Code return
#define by 0
#define MCYYDS ;
using namespace std;
int qpow(int a,int b,int p=INF){int ret=1;while(b){if(b&1)ret=(ret*a)%p;a=(a*a)%p;b>>=1;}return ret;}
inline int read(){int ret=0,f=1;char ch=getchar();while(ch<'0'||ch>'9')f=(ch=='-'?-1:f),ch=getchar();while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+(ch^48),ch=getchar();return ret*f;}
inline void write(int x){if(x<0){putchar('-');write(-x);return ;}if(x>9)write(x/10);putchar((char)(x%10+48));}
inline void writech(int x,char ch){write(x);putchar(ch);}
int n,m,p[205];
vector<pii > e[205],re[205];
vector<int> g[205],val[205];
bool f[205][40005],vis[205][25005];
int dis[205][25005];
priority_queue<pair<int,pii > > q;
stack<int> s;
bool cmp(pii x,pii y)
{return x.second<y.second;
}
signed main()
{
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);int T=read();while(T--){int n=read(),m=read();for(int i=1;i<=n;i++){p[i]=read();}for(int i=1;i<=m;i++){int u=read(),v=read(),w=read();e[u].pb({v,w});re[v].pb({u,w});if(w==1)g[u].pb(v); }for(int i=1;i<=n;i++){sort(e[i].begin(),e[i].end(),cmp);}f[1][1]=1;for(int i=1;i<=40000;i++){for(int j=1;j<=n;j++){if(f[j][i])s.push(j);}while(s.size()){int u=s.top();s.pop();for(auto v:g[u]){if(p[v]>=i&&!f[v][i]){f[v][i]=1;s.push(v);}}}for(int j=1;j<=n;j++){if(!f[j][i])continue;for(auto x:e[j]){int v=x.first,w=x.second;if(i*w<=40000&&i*w<=p[v])f[v][i*w]=1;}}}for(int i=1;i<=n;i++){memset(dis[i],0xcf,sizeof(dis[i]));}dis[n][1]=p[n];q.push({p[n],{n,1}});while(q.size()){int u=q.top().second.first,x=q.top().second.second;q.pop();if(vis[u][x])continue;vis[u][x]=1;for(auto y:re[u]){int v=y.first,w=y.second;if(x*w<=25000&&dis[v][x*w]<min(p[v],dis[u][x]/w)){dis[v][x*w]=min(p[v],dis[u][x]/w);q.push({dis[v][x*w],{v,x*w}});}}}for(int i=1;i<=40000;i++){for(int j=1;j<=n;j++){if(!f[j][i])continue;for(auto x:e[j]){val[x.first].pb(x.second*i);}}}int ans=-1;for(int i=1;i<=n;i++){sort(val[i].begin(),val[i].end());int r=25000;for(auto x:val[i]){while(r&&dis[i][r]<x)r--;if(r)ans=max(ans,r*x);}}writech(ans,'\n');for(int i=1;i<=n;i++){val[i].clear();e[i].clear();re[i].clear();g[i].clear();memset(f[i],0,sizeof(f[i]));memset(vis[i],0,sizeof(vis[i]));}}Code by MCYYDS
}