poj1847

题意：有N个城市，要求从A到B。接下来给出N行，每行第一个数字K表示可以去的城市的个数。接下来输入K个数字，第一个数字不需要按动开关，接下来每一个数字都需要1来转换。

建图的话，直接第一个数为0，接下去都构造1。又因为N不大，直接使用矩阵存图。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 using namespace std;
 5 const int inf=0x3f3f3f3f;
 6 int N,A,B;
 7 int mp[120][120];
 8 
 9 void spfa()
10 {
11     queue<int> iop;
12     int dist[120];
13     bool flag[120];
14     memset( flag, false, sizeof flag);
15     memset( dist, inf, sizeof dist);
16     iop.push(A);
17     flag[A]=true;
18     dist[A]=0;
19     while(!iop.empty()){
20         int kop=iop.front();
21         iop.pop();
22         for(int i=1;i<=N;i++){
23             if(dist[i]>dist[kop]+mp[kop][i]){
24                 dist[i]=dist[kop]+mp[kop][i];
25                 if(!flag[i]){
26                     flag[i]=true;
27                     iop.push(i);
28                 }
29             }
30         }
31         flag[kop]=false;
32     }
33     if(dist[B]==inf)
34         printf("-1
");
35     else
36         printf("%d
",dist[B]);
37 }
38 
39 int main()
40 {
41     while( ~scanf("%d%d%d",&N,&A,&B)){
42         memset( mp, inf, sizeof mp);
43         for(int i=1;i<=N;i++){
44             int x,y,z;
45             scanf("%d%d",&x,&y);
46             mp[i][y]=0;
47             for(int j=1;j<x;j++){
48                 scanf("%d",&z);
49                 mp[i][z]=1;
50             }
51         }
52         spfa();
53     }
54     return 0;
55 }