百度之星 鸽子 题解(dp)

题目链接

题目大意

其实是个简单题。。。。但是比较新颖

设\(dp[i][j]\)表示前\(i\)次操作，变为\(j\)的位置后的答案是多少

而每次交换只会影响\(u,v\)两个数的\(dp\)值，然后滚动一下数组即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=1e5+5,inf=0x3f3f3f3f,mod=998244353;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-7;
int n,m,k;
int dp[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _; cin>>_;
    while(_--){
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++){
            dp[i]=inf;
        }
        dp[k]=0;
        for(int i=1,u,v;i<=m;i++){
            cin>>u>>v;
            int x=dp[u],y=dp[v];
            dp[u]=min(y,x+1);
            dp[v]=min(x,y+1);
        }
        for(int i=1;i<=n;i++){
            if(dp[i]==inf) dp[i]=-1;
            printf("%d%c",dp[i],i==n?'\n':' ');
        }
    }
    return 0;
}