#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int MAXN = 51; int Graph[MAXN][MAXN],visit[MAXN]; int pre[MAXN]; int n,m,k; queue<int>myqueue; int bfs() { int h,i,dist[55]; memset(dist,0,sizeof(dist)); while (!myqueue.empty()) myqueue.pop(); myqueue.push(1); dist[1]=0; while (!myqueue.empty()) { h=myqueue.front(); myqueue.pop(); if (h==n) break; for (i=1; i<=n; i++) if (Graph[h][i] && !visit[i] && dist[i]==0) { dist[i]=dist[h]+1; pre[i]=h; myqueue.push(i); } } return dist[n]; } int solve(int cnt) { int dis = bfs(); if(dis > k||dis == 0){ return 1; } else if(cnt == 0){ return 0; } else { int way[55]; int j = pre[n]; int t = dis; while(j!=1) { way[--t] = j; j = pre[j]; } for(int i = 1; i < dis; i ++) { visit[way[i]] = 1; if(solve(cnt-1))return 1; visit[way[i]] = 0; } } return 0; } int main() { int x,y,cnt; while(scanf("%d%d%d",&n,&m,&k),n+m+k) { memset(Graph,0,sizeof(Graph)); memset(visit,0,sizeof(visit)); for(int i = 0; i < m; i ++) { scanf("%d%d",&x,&y); Graph[x][y] =1; } int dis = bfs(); if(dis > k||dis == 0){ cnt = 0; } else{ int way[55]; int j = pre[n]; int t = dis; while(j!=1){ way[--t] = j; j = pre[j]; } cnt = 0; int ok = 0; for(int i = 1; i <= n-1; i ++){ memset(visit,0,sizeof(visit)); for(int j = 1; j < dis; j ++){ visit[way[j]] = 1; if(solve(i-1)){ cnt = i; ok = 1; break; } visit[way[j]] = 0; } if(ok)break; } } printf("%d\n",cnt); } } |
Double click to view unformatted code.