http://poj.org/problem?id=1847
一个水题，用来熟悉熟悉spfa和floyd的。
题意：有m条的铁路，要从x,到y,
之后分别就是条铁路与其他铁路的交点。第一个输入的为有n个交点。之后第一个输入的点，当前铁路到这个点是不要转向的，也就是权值为0，其余的权值都为1，求从x到y的最短路，如果到不了输出-1
裸的floyd和spfa；
#include <stdio.h>
#include <string.h>
#define inf 0x3f3f int graph[][];
int m,n,x,y; void floyd()
{
int k,i,j;
for( k = ; k <= m ; k++ )
for( i = ; i <= m ; i++ )
for( j = ; j <= m ; j++)
if( graph[ i ][ j ] > graph[ i ][ k ] + graph[ k ][ j ] )
graph[ i ][ j ] = graph[ i ][ k ] + graph[ k ][ j ];
} int main()
{
// freopen("in.txt","r",stdin);
int tmp;
while(scanf("%d%d%d",&m,&x,&y)!=EOF)
{
for( int i = ; i <= m ; i++ )
for( int j = ; j <= m ; j++ )
if( i == j )
graph[ i ][ j ] = ;
else
graph[ i ][ j ] = inf;
for( int i = ; i <= m ; i++ )
{
scanf("%d",&n);
for( int j = ;j <= n ; j++ )
{
scanf("%d",&tmp);
if( j == )
graph[ i ][ tmp ] = ;
else
graph[ i ][ tmp ] = ;
}
}
floyd();
if( graph[ x ][ y ] != inf)
printf("%d\n",graph[ x ][ y ]);
else
printf("-1\n");
}
return ;
}
floyd
#include <stdio.h>
#include <string.h>
#include <queue>
#define maxn 101
#define inf 0x3f3f3f3f using namespace std; int m,x,n,y,pos,head[ maxn ]; int ans , dist[ maxn ]; bool vis[ maxn ]; struct note {
int v,w,next;
}edge[maxn]; void init()
{
pos = ;
for(int i = ;i <= n ; i++ ) dist[ i ] = inf;
memset( head , - , sizeof( head ) );
memset( vis , false ,sizeof( vis ) );
} void add(int x,int v,int w)
{
edge[ pos ].v = v;
edge[ pos ].w = w;
edge[ pos ].next = head[ x ];
head[ x ] = pos++;
} void spfa()
{
queue<int >s;
s.push(x);
vis[ x ] = true;
dist[ x ] = ;
while(!s.empty())
{
int tmp = s.front();
s.pop();
vis [ tmp ] = false;
for( int i = head[ tmp ] ; i != - ; i = edge[ i ].next )
{
if( dist[ edge[ i ].v ] > dist[ tmp ] + edge[ i ].w)
{
dist[ edge[ i ].v ] = dist[ tmp ] + edge[ i ].w;
if( !vis[ edge[ i ].v ] )
{
s.push( edge[ i ].v );
vis[ edge[ i ].v ] =true;
}
} }
}
} int main()
{
// freopen("in.txt","r",stdin);
while(~scanf("%d%d%d",&n,&x,&y))
{
init();
int tmp;
for(int j = ; j <= n ; j++ )
{
scanf("%d",&m);
for(int i = ; i <= m ; i++ )
{
scanf("%d",&tmp);
if( i == ) add( j , tmp , );
else add( j , tmp , );
}
}
spfa();
if( dist [ y ] == inf ) printf("-1\n");
else printf("%d\n",dist[ y ]);
}
return ;
}
spfa