很简单的最短路问题,其中的关键就在于有些农场是没有牛的,这些农场可以走,但不能算在最终答案中,毕竟题中需要的是牛的最短路径。将'Z'点作为源点,进行一次赤裸裸的单源点最短路径,就可以得出答案了。代码中我用一个hash函数把所有的字母下标点都规整到[1,52]这个范围内。
/* ID:sevenst4 LANG:C++ PROG:comehome */ #include<stdio.h> #define INF 0x0FFFFFFF using namespace std; int map[53][53]; int f( char a ) { if( a>='A' && a<='Z' ) return a-'A'+1; else return a-'a'+1+26; } void dij() { bool vis[53]; for( int i=0;i<53;i++ ) vis[i]=false; int p=f('Z'); vis[p]=true; for( int i=1;i<53;i++ ) { int min=INF; int index=-1; for( int j=1;j<53;j++ ) if( min>map[p][j] && vis[j]==false ) min=map[p][j],index=j; if( index==-1 ) return ; vis[index]=true; for( int j=1;j<53;j++ ) { if( map[p][j]>map[p][index]+map[index][j] ) map[p][j]=map[p][index]+map[index][j]; } } return ; } int main() { freopen( "comehome.in","r",stdin ); freopen( "comehome.out","w",stdout ); int n; for( int i=0;i<53;i++ ) for( int j=0;j<53;j++ ) map[i][j]=INF; scanf( "%d",&n ); for( int i=1;i<=n;i++ ) { char a,b,c;int len; scanf( "%c",&c ); scanf( "%c %c %d",&a,&b,&len ); if( map[f(a)][f(b)]>len ) map[f(a)][f(b)]=map[f(b)][f(a)]=len; } dij(); int min=INF;int index; for( int i=1;i<26;i++ ) if( min>map[f('Z')][i] ) { min=map[f('Z')][i]; index=i; } printf( "%c %d\n",char(index+'A'-1),min ); return 0; }
好久没写代码了... Dij都忘记了...