[U]2.4.4 Bessie Come Home 简单最短路问题

很简单的最短路问题，其中的关键就在于有些农场是没有牛的，这些农场可以走，但不能算在最终答案中，毕竟题中需要的是牛的最短路径。将'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;elsereturn 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;
}