hdu2485:http://acm.hdu.edu.cn/showproblem.php?pid=2485
题意：给你一个图，让你删除其中的一些点，然后使得1到n的最小距离大于k，求删除的最小的点数。
题解：DFS枚举最短路径上的点。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define inf 100000000 7 using namespace std; 8 const int N=55; 9 const int E=20000; 10 int dist[N],del[N][N],vis[N],head[N]; 11 bool visit[N]; 12 int n,m,k,cnt,ans,u,v,pre[N]; 13 struct Node{ 14 int v; 15 int next; 16 }edge[E]; 17 void init(){ 18 memset(head,-1,sizeof(head)); 19 memset(visit,0,sizeof(visit)); 20 memset(pre,0,sizeof(pre)); 21 cnt=0; 22 ans=inf; 23 } 24 void add(int u,int v){ 25 edge[cnt].v=v; 26 edge[cnt].next=head[u]; 27 head[u]=cnt++; 28 } 29 bool BFS(){ 30 for(int i=1;i<=n;i++){ 31 dist[i]=inf; 32 vis[i]=false; 33 } 34 queue<int>Q; 35 vis[1]=1; 36 dist[1]=0; 37 Q.push(1); 38 while(!Q.empty()){ 39 int u=Q.front(); 40 Q.pop(); 41 vis[u]=0; 42 for(int i=head[u];i!=-1;i=edge[i].next){ 43 int v=edge[i].v; 44 if(!visit[v]&&dist[v]>dist[u]+1){ 45 dist[v]=dist[u]+1; 46 pre[v]=u; 47 if(!vis[v]){ 48 Q.push(v); 49 vis[v]=1; 50 } 51 if(v==n&&dist[v]<=k)return true; 52 } 53 } 54 } 55 return false; 56 } 57 void DFS(int depth){ 58 if(depth>=ans)return; 59 memset(pre,0,sizeof(pre)); 60 if(!BFS()){ 61 ans=min(ans,depth); 62 return; 63 } 64 int num=0; 65 for(int i=pre[n];i!=1;i=pre[i]){ 66 del[depth][++num]=i; 67 } 68 for(int i=1;i<=num;i++){ 69 visit[del[depth][i]]=true; 70 DFS(depth+1); 71 visit[del[depth][i]]=false; 72 } 73 } 74 75 int main(){ 76 while(~scanf("%d%d%d",&n,&m,&k)&&n){ 77 init(); 78 for(int i=1;i<=m;i++){ 79 scanf("%d%d",&u,&v); 80 add(u,v); 81 } 82 DFS(0); 83 printf("%d ",ans); 84 } 85 }