一个水题，用来熟悉熟悉spfa和floyd的。
题意：有m条的铁路，要从x,到y,
之后分别就是条铁路与其他铁路的交点。第一个输入的为有n个交点。之后第一个输入的点，当前铁路到这个点是不要转向的，也就是权值为0，其余的权值都为1，求从x到y的最短路，如果到不了输出-1
裸的floyd和spfa；
1 #include2 #include 3 #define inf 0x3f3f 4 5 int graph[105][105]; 6 int m,n,x,y; 7 8 void floyd() 9 {10 int k,i,j;11 for( k = 1 ; k <= m ; k++ )12 for( i = 1 ; i <= m ; i++ )13 for( j = 1 ; j <= m ; j++)14 if( graph[ i ][ j ] > graph[ i ][ k ] + graph[ k ][ j ] )15 graph[ i ][ j ] = graph[ i ][ k ] + graph[ k ][ j ];16 }17 18 int main()19 {20 // freopen("in.txt","r",stdin);21 int tmp;22 while(scanf("%d%d%d",&m,&x,&y)!=EOF)23 {24 for( int i = 1 ; i <= m ; i++ )25 for( int j = 1 ; j <= m ; j++ )26 if( i == j )27 graph[ i ][ j ] = 0;28 else29 graph[ i ][ j ] = inf;30 for( int i = 1 ; i <= m ; i++ )31 {32 scanf("%d",&n);33 for( int j = 1 ;j <= n ; j++ )34 {35 scanf("%d",&tmp);36 if( j == 1 )37 graph[ i ][ tmp ] = 0;38 else39 graph[ i ][ tmp ] = 1;40 }41 }42 floyd();43 if( graph[ x ][ y ] != inf)44 printf("%d\n",graph[ x ][ y ]);45 else46 printf("-1\n");47 }48 return 0;49 }
1 #include2 #include 3 #include 4 #define maxn 101 5 #define inf 0x3f3f3f3f 6 7 using namespace std; 8 9 int m,x,n,y,pos,head[ maxn ];10 11 int ans , dist[ maxn ];12 13 bool vis[ maxn ];14 15 struct note {16 int v,w,next;17 }edge[maxn];18 19 void init()20 {21 pos = 1;22 for(int i = 1 ;i <= n ; i++ ) dist[ i ] = inf;23 memset( head , -1 , sizeof( head ) );24 memset( vis , false ,sizeof( vis ) );25 }26 27 void add(int x,int v,int w)28 {29 edge[ pos ].v = v;30 edge[ pos ].w = w;31 edge[ pos ].next = head[ x ];32 head[ x ] = pos++;33 }34 35 void spfa()36 {37 queue s;38 s.push(x);39 vis[ x ] = true;40 dist[ x ] = 0;41 while(!s.empty())42 {43 int tmp = s.front();44 s.pop();45 vis [ tmp ] = false;46 for( int i = head[ tmp ] ; i != -1 ; i = edge[ i ].next )47 {48 if( dist[ edge[ i ].v ] > dist[ tmp ] + edge[ i ].w)49 {50 dist[ edge[ i ].v ] = dist[ tmp ] + edge[ i ].w;51 if( !vis[ edge[ i ].v ] )52 {53 s.push( edge[ i ].v );54 vis[ edge[ i ].v ] =true;55 }56 }57 58 }59 }60 }61 62 int main()63 {64 // freopen("in.txt","r",stdin);65 while(~scanf("%d%d%d",&n,&x,&y))66 {67 init();68 int tmp;69 for(int j = 1 ; j <= n ; j++ )70 {71 scanf("%d",&m);72 for(int i = 1 ; i <= m ; i++ )73 {74 scanf("%d",&tmp);75 if( i == 1 ) add( j , tmp , 0);76 else add( j , tmp , 1 );77 }78 }79 spfa();80 if( dist [ y ] == inf ) printf("-1\n");81 else printf("%d\n",dist[ y ]);82 }83 return 0;84 }