CSU 1256

 1 #include <stdio.h>
 2 #include <queue>
 3 using namespace std;
 4 const int maxm = 20010;//两倍！！！！
 5 const int maxn = 5010;
 6 const int maxd = 9999;
 7 int v[maxm],w[maxm],next[maxm];
 8 int first[maxn],d[maxn],inq[maxn],e;
 9 
10 void init()
11 {
12     for(int i =0;i<maxn;i++)
13         first[i] = -1;
14     e = 0;
15 }
16 
17 void addeage(int x,int y,int z)
18 {
19     v[e]=y;
20     w[e]=z;
21     next[e]=first[x];
22     first[x]=e;
23     e++;
24 }
25 
26 void spfa(int s)
27 {
28     queue<int> q;
29     for(int i =0;i<maxn;i++)
30         d[i]=maxd;
31     d[s] = 0;
32     inq[s] = 1;
33     q.push(s);
34 
35     while(!q.empty())
36     {
37         int u = q.front();
38         q.pop();
39         inq[u]=0;
40         for(int i =first[u];i!=-1;i=next[i])
41         {
42             if(d[v[i]]>d[u]+w[i])
43             {
44                 d[v[i]]=d[u]+w[i];
45                 if(inq[v[i]]==0)
46                 {
47                     q.push(v[i]);
48                     inq[v[i]]=1;
49                 }
50             }
51         }
52     }
53 }
54 
55 int main()
56 {
57     int n,m,a,b;
58     while(scanf("%d%d",&n,&m)!=EOF)
59     {
60         init();
61         for(int i = 0;i<m;i++)
62         {
63             scanf("%d%d",&a,&b);
64             addeage(a,b,0);
65             addeage(b,a,1);
66         }
67         spfa(1);
68         if(d[n]!=maxd)
69             printf("%d\n",d[n]);
70         else
71              printf("%d\n",-1);
72     }
73     return 0;
74 }