2 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=210,inf=0x3f3f3f3f; int w[N],a[N][N],d[N][N],mp[N][N],fa[N],id[N]; int findfa(int x){ return fa[x]==x?fa[x]:fa[x]=findfa(fa[x]);} int main() { int m;scanf("%d",&m); memset(mp,0,sizeof(mp)); for(int x,y,L1,L2,i=1;i<=m;i++) { scanf("%d",&x); scanf("%d%d%d",&w[x],&L1,&L2); for(int j=1;j<=L1;j++) scanf("%d",&y),mp[x][y]=2*x-1; for(int j=1;j<=L2;j++) scanf("%d",&y),mp[x][y]=2*x; } for(int i=1;i<=2*m;i++) fa[i]=i; for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(mp[i][j]) { int x=mp[i][j],y=mp[j][i]; x=findfa(x);y=findfa(y); if(x!=y)fa[x]=y; } int n=0;memset(id,0,sizeof(id)); for(int i=1;i<=2*m;i++) { int x=findfa(i); if(id[x]==0) id[i]=id[x]=++n; else id[i]=id[x]; } memset(a,0x0f,sizeof(a)); for(int i=1;i<=m;i++) { int x=id[2*i-1],y=id[2*i]; a[x][y]=a[y][x]=w[i]; } int ans=25500; memcpy(d,a,sizeof(a)); for(int k=1;k<=n;k++) { for(int i=1;i<k;i++)for(int j=i+1;j<k;j++) ans=min(ans,d[i][j]+a[i][k]+a[k][j]); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } printf("%lld\n",ans); return 0; } -
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=210,inf=0x3f3f3f3f; int w[N],a[N][N],d[N][N],mp[N][N],fa[N],id[N]; int findfa(int x){ return fa[x]==x?fa[x]:fa[x]=findfa(fa[x]);} int main() { int m;scanf("%d",&m); memset(mp,0,sizeof(mp)); for(int x,y,L1,L2,i=1;i<=m;i++) { scanf("%d",&x); scanf("%d%d%d",&w[x],&L1,&L2); for(int j=1;j<=L1;j++) scanf("%d",&y),mp[x][y]=2*x-1; for(int j=1;j<=L2;j++) scanf("%d",&y),mp[x][y]=2*x; } for(int i=1;i<=2*m;i++) fa[i]=i; for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)if(mp[i][j]) { int x=mp[i][j],y=mp[j][i]; x=findfa(x);y=findfa(y); if(x!=y)fa[x]=y; } int n=0;memset(id,0,sizeof(id)); for(int i=1;i<=2*m;i++) { int x=findfa(i); if(id[x]==0) id[i]=id[x]=++n; else id[i]=id[x]; } memset(a,0x0f,sizeof(a)); for(int i=1;i<=m;i++) { int x=id[2*i-1],y=id[2*i]; a[x][y]=a[y][x]=w[i]; } int ans=25500; memcpy(d,a,sizeof(a)); for(int k=1;k<=n;k++) { for(int i=1;i<k;i++)for(int j=i+1;j<k;j++) ans=min(ans,d[i][j]+a[i][k]+a[k][j]); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]); } printf("%lld\n",ans); return 0; }
- 1
信息
- ID
- 1039
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 5
- 标签
- 递交数
- 23
- 已通过
- 14
- 上传者