文章

大众爱情(2022天梯赛L2-4)

大众爱情1.png大众爱情2.png

#include<bits/stdc++.h>
using namespace std;
//typedef long long ll;
int  maxn=1e9+10;
int a[1001][1001];//存储边的关系 
int sex[1001];//性别 男1 女0 
int dist[1001];//最短距离 
void show(int n){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%9d ",a[i][j]);
        }cout<<endl;
    }
    return ;
}
int main()
{
    char t;
    int n,i,j,k,s,mloc=-1,wloc=-1,r,way,flag,cnt;
    cin>>n;
    for(i=1;i<=n;i++){//初始化 
        dist[i]=maxn;
        for(j=1;j<=n;j++){
            a[i][j]=maxn;
        }
    }
    for(i=1;i<=n;i++){
        a[i][0]=-1;
        a[i][i]=0;
    }
    for(i=1;i<=n;i++){
        cin>>t;
        if(t=='M') sex[i]=1;
        cin>>s;
        for(cnt=1;cnt<=s;cnt++){
            scanf("%d:%d",&r,&way);
            a[i][r]=way;
        }
    }
    
//  show(n);
//  cout<<endl;
​
    for(k=1;k<=n;k++){//经过第k个点 
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
            }
        }
    }
//  show(n);
​
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            if(sex[i]+sex[j]==1){
                if(a[i][0]==-1||a[i][0]<a[j][i]){
                    a[i][0]=a[j][i];
                }
            }
        }
    }
    for(i=1;i<=n;i++){
        if(sex[i]==1){//man
            if(mloc==-1||mloc>a[i][0]){
                mloc=a[i][0];
            }
        }else {//woman
            if(wloc==-1||wloc>a[i][0]){
                wloc=a[i][0];
            }
        }
    }
    flag=0;//woman
    for(i=1;i<=n;i++){
        if(sex[i]==0&&a[i][0]==wloc){
            if(flag==0){
                flag=1;
            }else cout<<' ';
            cout<<i;
        }
    }cout<<endl;
    
    
    flag=0;//man
    for(i=1;i<=n;i++){
        if(sex[i]==1&&a[i][0]==mloc){
            if(flag==0){
                flag=1;
            }else cout<<' ';
            cout<<i;
        }
    }cout<<endl;
    return 0;
}

原题链接

https://pintia.cn/problem-sets/994805046380707840/exam/problems/1518582589840875520

License:  CC BY 4.0