搜索

每次找出最短路 如果小于等于k 那么必定这里有一点是要被删掉的

枚举这个最短路径上的每一个点 (一般不会超过20) 将其相邻边删除

用dijskra求最短路径并且保存即可

深度搜索

#include<cstdio>

#include<cstring>

#define maxn 1000000

bool kill[51],p[51][51],pd[51];

int dist[51],ans,n,m,k;

void dfs(int pans)

{

    if(pans>=ans) return;

    int i,j,pre[50],minj,minn;

    for(i=1;i<=n;i++)

        if(p[1][i]&&!kill[i]) {dist[i]=1;pre[i]=1;}

        else dist[i]=maxn;

    memset(pd,0,sizeof(pd));

    dist[1]=0;

    pd[1]=1;

    for(i=2;i<=n;i++){

        minn=maxn;

        for(j=1;j<=n;j++)

            if(dist[j]<minn&&!pd[j]){

                minn=dist[j];

                minj=j;

            }

        if(minn==maxn) break;

        pd[minj]=1;

        for(j=1;j<=n;j++)

            if(dist[j]>dist[minj]+1&&!pd[j]&&p[minj][j]&&!kill[j]){

                dist[j]=dist[minj]+1;

                pre[j]=minj;

            }

    }

    if(dist[n]<=k){

        j=pre[n];

        while(j!=1){

            kill[j]=1;

            dfs(pans+1);

            kill[j]=0;

            j=pre[j];

        }

    }

    else if(ans>pans) ans=pans;

}

int main()

{

    int i,j,x,y;

    while(1){

        ans=maxn;

        scanf("%d%d%d",&n,&m,&k);

        if(n==0) break;

        memset(p,0,sizeof(p));

        memset(kill,0,sizeof(0));

        for(i=1;i<=m;i++){

            scanf("%d%d",&x,&y);

            p[x][y]=1;

        }

        dfs(0);

        printf("%d\n",ans);

    }

    return 0;

}