分析：计算几何、最短路、字符串、hash。
首先，利用hash建立地名（单词）和编号的映射；
然后，将大地坐标转换，求出有直达航班地点之间的球面最短距离；
d = r*sqrt(2-2*(cos(lat1)*cos(lat2)*cos(lon1-lon2)+sin(lat1)*sin(lat2)) （推导见11817）
最后，利用floyd计算所有点间的最短距离，查询输出即可。
注意：1.有向图；2.距离取整要在计算最短路之前（四舍五入）；
#include#include #include #include #include using namespace std; //hash__begin typedef struct hnode { int id; char name[ 21 ]; hnode* next; }hnode; hnode* List[ 257 ]; hnode Node[ 105 ]; int table[20]={ 13,17,31,71,131,171,313,717,1313,1717, 3131,7171,13131,17171,31313,71717,131313, 171717,313131,717171}; class hash { int size; public: hash() { size = 0; memset( List, 0, sizeof(List) ); } //计算hash值 int calc( char* str ) { int value = 0; for ( int i = 0 ; str[i] ; ++ i ) value = (value+str[i]*table[i])%257; return value; } //插入 void insert( char* str, int id ) { int value = calc(str); Node[size].next = List[value]; Node[size].id = id; List[value] = &Node[size]; strcpy(Node[size ++].name,str); } //查询 int find( char* str ) { int value = calc(str); for ( hnode* p = List[value] ; p ; p = p->next ) if ( !strcmp( str, p->name ) ) return p->id; } }; //hash__end char name[105][21]; char city1[21],city2[21]; double lat[105],lon[105],dis; int path[105][105]; //大地坐标转化 int dist( double l1, double d1, double l2, double d2 ) { double r = 6378; double p = 3.141592653589793; l1 *= p/180.0; l2 *= p/180.0; d1 *= p/180.0; d2 *= p/180.0; double d = r*sqrt(2-2*(cos(l1)*cos(l2)*cos(d1-d2)+sin(l1)*sin(l2))); return (int)(0.5+2*asin(d/(2*r))*r); } //floyd计算多元最短路 void floyd( int n ) { for ( int k = 0 ; k < n ; ++ k ) for ( int i = 0 ; i < n ; ++ i ) for ( int j = 0 ; j < n ; ++ j ) if ( path[i][k] != -1 && path[k][j] != -1 ) if ( path[i][j] == -1 || path[i][j] > path[i][k] + path[k][j] ) path[i][j] = path[i][k] + path[k][j]; } int main() { int N,M,Q,id1,id2,T = 1; while ( ~scanf("%d%d%d",&N,&M,&Q) && N+M+Q ) { if ( T > 1 ) printf("\n"); printf("Case #%d\n",T ++); //输入数据到hash表 hash Hash; for ( int i = 0 ; i < N ; ++ i ) { scanf("%s%lf%lf",name[i],&lat[i],&lon[i]); Hash.insert( name[i], i ); } //初始化距离，只计算可直达 for ( int i = 0 ; i < N ; ++ i ) for ( int j = 0 ; j < N ; ++ j ) path[i][j] = -1; for ( int i = 0 ; i < M ; ++ i ) { scanf("%s%s",city1,city2); id1 = Hash.find( city1 ); id2 = Hash.find( city2 ); path[id1][id2] = dist( lat[id1], lon[id1], lat[id2], lon[id2] ); } //计算有向图多元最短路 floyd( N ); //查询输出 for ( int i = 0 ; i < Q ; ++ i ) { scanf("%s%s",city1,city2); id1 = Hash.find( city1 ); id2 = Hash.find( city2 ); if ( path[id1][id2] == -1 ) printf("no route exists\n"); else printf("%d km\n",path[id1][id2]); } } return 0; }