记录编号 |
581749 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
[CSP 2022S]假期计划 |
最终得分 |
100 |
用户昵称 |
宇战 |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
4.213 s |
提交时间 |
2023-08-12 16:10:49 |
内存使用 |
173.53 MiB |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,m,kk,maxn=-1;
int d[2501][2501],cnt,dp[2501][4],vis2[2501][6][2501],q[2501][6][6];
int val[2501],vis[2501],head[2501],step[2501];
int que[2501];
struct Edge{
int next;
int to;
int w;
}edge[30001];
void add_edge(int u,int v)
{
cnt++;
edge[cnt].to=v;
edge[cnt].w=1;
edge[cnt].next=head[u];
head[u]=cnt;
}
int main()
{
freopen("csp2022_holiday.in","r",stdin);
freopen("csp2022_holiday.out","w",stdout);
memset(d,0x3f,sizeof(d));
memset(dp,-0x3f,sizeof(dp));
memset(head,-1,sizeof(head));
cin>>n>>m>>kk;
for(int i=2;i<=n;i++)
{
cin>>val[i];
d[i][i]=0;
}
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
add_edge(x,y);
add_edge(y,x);
}
for(int i=1;i<=n;i++)
{
memset(step,0,sizeof(step));
memset(vis,0,sizeof(vis));
memset(que,0,sizeof(que));
que[1]=i;
vis[i]=1;
int hea=0,tail=1;
while(hea<tail)
{
hea++;
int u=que[hea];
int sat=step[hea];
d[i][u]=sat;
if(d[i][u]-1>kk) d[i][u]=d[0][0];
for(int j=head[u];j!=-1;j=edge[j].next)
{
int v=edge[j].to;
if(vis[v]==0)
{
step[++tail]=step[hea]+1;
que[tail]=v;
vis[v]=1;
}
}
}
}
for(int i=2;i<=n;i++)
{
if(d[1][i]!=d[0][0])
{
dp[i][1]=val[i];
vis2[i][1][i]=1;
q[i][1][1]=i;
}
}
for(int k=2;k<=4;k++)
{
for(int i=2;i<=n;i++)
{
int tmp=0;
for(int j=2;j<=n;j++)
{
if(d[i][j]==d[0][0]||i==j||d[i][j]<0) continue;
if(vis2[j][k-1][i]==1) continue;
if(dp[j][k-1]!=dp[0][0])
{
if(dp[j][k-1]>dp[i][k])
{
dp[i][k]=dp[j][k-1];
tmp=j;
}
}
}
for(int j=1;j<=n;j++)
{
q[i][k][j]=q[tmp][k-1][j];
vis2[i][k][q[i][k][j]]=1;
if(q[i][k][j]==0)
{
q[i][k][j]=i;
vis2[i][k][i]=1;
break;
}
}
dp[i][k]+=val[i];
}
}
for(int i=2;i<=n;i++)
{
if(d[i][1]!=d[0][0])
{
maxn=max(maxn,dp[i][4]);
}
}
cout<<maxn;
return 0;
}