鸽子（线性DP）

题目链接
题目描述：

思路分析：
DP[i][j]表示将初始位置为K的电脑进行第i次操作后当前位置为j的最小不执行命令次数。
这题的DP方程是真的巧妙，因为我们考虑的是初始位置为K的电脑最终放在j位置的最小不执行次数，所以每一个交换命令意味着，1、这一层交换不执行，坏电脑在X位置的最小并不执行次数就是就在上一层状态x不执行次数加一，2、执行就是坏电脑在Y的位置移到了X位置，所以坏电脑在X位置的最小不执行次数就等于上一层坏电脑在Y位置的最小不移动次数（第一次见这样的状态转移方式记录一下）。因为每一层只交换命令的x,y，其他位置不变所以时间复杂度为O（m).

题目代码：

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int t;
int n,m,k;
struct ty{
    int x;
    int y;
};
ty a[100005];
int f[2][100005];
int main(){
    scanf(" %d",&t);
    while(t--){
        scanf(" %d %d %d",&n,&m,&k);
        for(int i=1;i<=m;i++) scanf(" %d %d",&a[i].x,&a[i].y);
        for(int i=0;i<=1;i++){
            for(int j=0;j<=100001;j++) f[i][j]=INF;
        }
        f[0][k]=0;
        f[1][k]=0;
        for(int i=1;i<=m;i++){
            //for(int j=1;j<=n;j++) f[i&1][j]=f[(i-1)&1][j];
            int x=a[i].x,y=a[i].y;
            /*1、这一层交换不执行，坏电脑在X位置的最小并不执行次数就是就在上一层状态x不执行次数加一
            2、执行就是坏电脑在Y的位置移到了X位置，
            所以坏电脑在X位置的最小不执行次数就等于上一层坏电脑在Y位置的最小不移动次数 */
            f[i&1][x]=min(f[(i-1)&1][y],f[(i-1)&1][x]+1);
            f[i&1][y]=min(f[(i-1)&1][x],f[(i-1)&1][y]+1);
            f[(i+1)&1][x]=f[i&1][x];
            f[(i+1)&1][y]=f[i&1][y];
            //for(int j=1;j<=n;j++) cout<<f[i&1][j]<<" ";
            //cout<<"\n";
        }
        for(int i=1;i<=n;i++){
            if(i!=n){
                if(f[m&1][i]!=INF) printf("%d ",f[m&1][i]);
                else printf("-1 ");
            }
            else{
                if(f[m&1][i]!=INF) printf("%d",f[m&1][i]);
                else printf("-1");
            }
        }
        cout<<"\n";
    }
    return 0;
}