CSUOJ 1256 天朝的单行道

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <queue>
 5 using namespace std;
 6 #define N 5005
 7 #define M 20010
 8 #define MAXN 0x3f3f3f3f
 9 int first[N],k,visit[N],dp[N];//对应i城市第一条道路的下标,k表示路的条数
10 
11 struct Path{
12     int y,next,d;//y表示终点，next从同一起点出发对应的下一条路的下标，d表示路的长度
13 }path[M];
14 
15 void add(int x,int y,int a){
16     path[k].y=y,path[k].d=a,path[k].next=first[x];
17     first[x]=k;
18     k++;
19 }
20 
21 void spfa(int a){
22     memset(dp,0x3f,sizeof(dp));
23     queue<int> q;
24     dp[a]=0,visit[a]=1;
25     q.push(a);
26     while(!q.empty()){
27         int b=q.front();
28         q.pop();
29         visit[b]=0;
30         for(int i=first[b];i!=-1;i=path[i].next){
31             if(dp[path[i].y]>dp[b]+path[i].d){
32                 dp[path[i].y]=dp[b]+path[i].d;
33                 if(!visit[path[i].y]) visit[path[i].y]=1,q.push(path[i].y);
34             }
35         }
36     }
37 }
38 
39 int main()
40 {
41     int n,m,u,v;
42     while(scanf("%d%d",&n,&m)!=EOF){
43         memset(first,-1,sizeof(first));
44         k=0;
45         for(int i=0;i<m;i++)
46         {
47             scanf("%d%d",&u,&v);
48             add(u,v,0);
49             add(v,u,1);
50         }
51         spfa(1);
52         if(dp[n]<MAXN) cout<<dp[n]<<endl;
53         else cout<<-1<<endl;
54     }
55     return 0;
56 }