比赛 |
2024暑假C班集训C |
评测结果 |
WWWATTTTTT |
题目名称 |
喵星人集会 |
最终得分 |
10 |
用户昵称 |
123 |
运行时间 |
11.450 s |
代码语言 |
C++ |
内存使用 |
3.43 MiB |
提交时间 |
2024-07-12 11:28:57 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=55;
char s[N];
int n,g[N][N],dp[N][N],dis[N],vis[N],ret=1e9,f=0,flag[N],now[N];
int dijstra(int s,int t)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
for (int i=1;i<n;i++)
{
int mi=1e9,cnt=0;
for (int j=1;j<=n;j++)
{
if (!vis[j] && dis[j]<mi)
{
mi=dis[j];
cnt=j;
}
}
vis[cnt]=1;
for (int j=1;j<=n;j++)
{
if (dis[j]>dis[cnt]+1 && g[j][cnt])
{
dis[j]=dis[cnt]+1;
}
}
}
return dis[t];
}
void dfs(int step,int cnt)
{
if (step==f+1)
{
int e=0;
for (int i=1;i<=n;i++)
{
if (flag[i])
{
if (e) return ;
while (flag[i]) i++;
e=1;
}
}
if (cnt<ret)
{
ret=cnt;
}
return ;
}
if (cnt>ret)
{
return ;
}
for (int i=1;i<=n;i++)
{
if (!flag[i])
{
flag[i]=1;
dfs(step+1,cnt+dp[i][now[step]]);
flag[i]=0;
}
}
}
int main() {
freopen("party.in","r",stdin);
freopen("party.out","w",stdout);
scanf("%d%s",&n,s);
for (int i=0;i<n;i++)
{
if (s[i]=='1')
{
now[++f]=i+1;
}
}
for (int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
g[a][b]=g[b][a]=1;
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
dp[i][j]=dijstra(i,j);
}
}
dfs(1,0);
printf("%d",ret);
}