Fair

一个题目数据小就是那个题目的突破点(一般),比如这个题目,大家貌似都能想到n^2的,但是大家看一眼k的大小会发现,这题的突破点在k(这题不是水题= - =).考虑对于没种颜色做一次bfs,算出其他点到这种颜色的最短距离.
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=105;
int w[N],ans[N];
vector<int>v[N];
int dis[N][M];
vector<int>col[M];
int vis[N];
queue<int>q;
void bfs(int x)
{
    while(q.size())
    {
        int temp=q.front();
        q.pop();
        for(int i=0;i<v[temp].size();i++)
        {
            int pos=v[temp][i];
            if(vis[pos]) continue;
            q.push(pos);
            dis[pos][x]+=dis[temp][x]+1;
            vis[pos]=1;
        }
    }
}

int main()
{
    int n,m,k,s;
    //memset(dis,-1,sizeof dis);
    scanf("%d%d%d%d",&n,&m,&k,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);//输入每个点的颜色.
        col[w[i]].push_back(i);
    }
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=k;i++)
    {
        memset(vis,0,sizeof vis);
        for(int j=0;j<col[i].size();j++)
        {
            q.push(col[i][j]);
            vis[col[i][j]]=1;
            dis[col[i][j]][i]=0;
        }
        bfs(i);
    }
    for(int i=1;i<=n;i++)
    {
        sort(dis[i]+1,dis[i]+1+k);
        for(int j=1;j<=s;j++)
        {
           // if(i==1) cout<<dis[i][j]<<' ';
            ans[i]+=dis[i][j];
        }
    }//cout<<endl;
    for(int i=1;i<=n;i++) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}