UVa 10075 - Airlines

题目：给出地球上一些点的经度和纬度，以及地点之间是否直达的航班，然后询问两地间最短的行程。

分析：计算几何、最短路、字符串、hash。

            首先，利用hash建立地名（单词）和编号的映射；

            然后，将大地坐标转换，求出有直达航班地点之间的球面最短距离；

            d = r*sqrt(2-2*(cos(lat1)*cos(lat2)*cos(lon1-lon2)+sin(lat1)*sin(lat2)) （推导见11817）

            最后，利用floyd计算所有点间的最短距离，查询输出即可。

注意：1.有向图；2.距离取整要在计算最短路之前（四舍五入）；

            3.早上起来改用了不同版本的最短路算法，效率差强人意，效率和代码如下：

               T：dijkstra+斐波那契堆 < spfa+stack < dijkstra+二叉堆 = floyd < dijkstra+二项堆 = TLE。

#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__endchar   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;
}

早上起来，改了不同的最短路算法，发现效率没有明显提高，╮(╯▽╰)╭。

spfa版本：

#include 
#include 
#include 
#include 
#include using namespace std;const int MAX_LENGTH = 5000000;//hash__begin
typedef struct hnode
{int    id;char   name[ 21 ];hnode* next;
}hnode;
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;hnode* List[ 257 ];hnode  Node[ 105 ];
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__endchar   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);	
}//邻接表
typedef struct nodeg 
{int    point;int    length;nodeg* next;
}graph ;
graph* Head[105];
graph  Edge[305];
int    Count;
int    visit[105];
//初始化 
void initgraph( int n )
{for ( int i = 0 ; i < n ; ++ i )for ( int j = 0 ; j < n ; ++ j )path[i][j] = MAX_LENGTH;for ( int i = 0 ; i < n ; ++ i )path[i][i] = 0;for ( int i = 0 ; i < n ; ++ i )visit[i] = 0;for ( int i = 0 ; i < n ; ++ i )Head[i] = NULL;Count = 0;
}
//插入边 
void addedge( int point1, int point2, int length )
{Edge[Count].point  = point2;Edge[Count].length = length;Edge[Count].next   = Head[point1];Head[point1] = &Edge[Count ++];
}
//邻接表 end //SPFA计算最短路径 
int Stack[105];
int spfa( int s, int t, int n )
{	Stack[0] = s;visit[s] = 1;int top  = 1;while ( top ) {int now = Stack[-- top];for ( graph* p = Head[now] ; p ; p = p->next ) if ( path[s][p->point] > path[s][now] + p->length ) {path[s][p->point] = path[s][now] + p->length;if ( !visit[p->point] ) {visit[p->point] = 1;Stack[top ++] = p->point;}}visit[now] = 0;}return path[s][t];
}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 );}//初始化距离，只计算可直达 initgraph( N );for ( int i = 0 ; i < M ; ++ i ) {scanf("%s%s",city1,city2);id1 = Hash.find( city1 );id2 = Hash.find( city2 );addedge( id1, id2, dist( lat[id1], lon[id1], lat[id2], lon[id2] ) );}//计算有向图多元最短路 for ( int i = 0 ; i < N ; ++ i )spfa( i, i, 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] == MAX_LENGTH )printf("no route exists\n");else printf("%d km\n",path[id1][id2]);}}return 0;
}

#include 
#include 
#include 
#include 
#include using namespace std;const int MAX_LENGTH = 5000000;//hash__begin
typedef struct hnode
{int    id;char   name[ 21 ];hnode* next;
}hnode;
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;hnode* List[ 257 ];hnode  Node[ 105 ];
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__endchar   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);	
}//邻接表
typedef struct nodeg 
{int    point;int    length;nodeg* next;
}graph ;
graph* Head[105];
graph  Edge[305];
int    Count;
int    visit[105];
//初始化 
void initgraph( int n )
{for ( int i = 0 ; i < n ; ++ i )for ( int j = 0 ; j < n ; ++ j )path[i][j] = MAX_LENGTH;for ( int i = 0 ; i < n ; ++ i )path[i][i] = 0;for ( int i = 0 ; i < n ; ++ i )visit[i] = 0;for ( int i = 0 ; i < n ; ++ i )Head[i] = NULL;Count = 0;
}
//插入边 
void addedge( int point1, int point2, int length )
{Edge[Count].point  = point2;Edge[Count].length = length;Edge[Count].next   = Head[point1];Head[point1] = &Edge[Count ++];
}
//邻接表 end //heap
class banery_heap
{private:int  size;int  keys[105];int  base[105];int  In_h[105];public:banery_heap( int count = 100 ) {clear();}void clear() {size = 0;memset( base, 0, sizeof( base ) );memset( keys, 0, sizeof( keys ) );memset( In_h, 0, sizeof( In_h ) );}bool empty(){return size == 0;}void Insert( int ID, int Key ) {if ( !In_h[ID] ) {In_h[ID] = ++ size;base[size] = ID;}keys[In_h[ID]] = Key;int now = In_h[ID];while ( now > 1 && keys[now] < keys[now>>1] ) {swap( base[now], base[now>>1] );swap( keys[now], keys[now>>1] );swap( In_h[base[now]], In_h[base[now>>1]] );now = now>>1;}}int Delete( void ) {swap( base[size], base[1] );swap( keys[size], keys[1] );swap( In_h[base[size]], In_h[base[1]] );int now = 1;while ( 1 ) {int New = now,L = (now<<1),R = (now<<1)+1;if ( L < size && keys[L] < keys[New] ) New = L;if ( R < size && keys[R] < keys[New] ) New = R;if ( now == New ) break;swap( base[now], base[New] );swap( keys[now], keys[New] );swap( In_h[base[now]], In_h[base[New]] );now = New;}return base[size --];}
}Heap;
//heap endvoid dijkstra( int s, int n )
{Heap.clear();Heap.Insert( s, 0 );while ( !Heap.empty() ) {int now = Heap.Delete();for ( graph* p = Head[now] ; p ; p = p->next )if ( path[s][p->point] > path[s][now] + p->length ) {path[s][p->point] = path[s][now] + p->length;Heap.Insert( p->point, path[s][p->point] );}}
}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 );}//初始化距离，只计算可直达 initgraph( N );for ( int i = 0 ; i < M ; ++ i ) {scanf("%s%s",city1,city2);id1 = Hash.find( city1 );id2 = Hash.find( city2 );addedge( id1, id2, dist( lat[id1], lon[id1], lat[id2], lon[id2] ) );}//计算有向图多元最短路 for ( int i = 0 ; i < N ; ++ i )spfa( i, 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] == MAX_LENGTH )printf("no route exists\n");else printf("%d km\n",path[id1][id2]);}}return 0;
}

dijkstra+fibonacci_heap版本：

#include 
#include 
#include 
#include 
#include using namespace std;const int MAX_LENGTH = 5000000;//hash__begin
typedef struct hnode
{int    id;char   name[ 21 ];hnode* next;
}hnode;
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;hnode* List[ 257 ];hnode  Node[ 105 ];
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__endchar   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);	
}//邻接表
typedef struct gnode
{int    point;int    length;gnode* next;
}graph ;
graph* Head[105];
graph  Edge[305];
int    Count;
int    visit[105];
//初始化 
void initgraph( int n )
{for ( int i = 0 ; i < n ; ++ i )for ( int j = 0 ; j < n ; ++ j )path[i][j] = MAX_LENGTH;for ( int i = 0 ; i < n ; ++ i )path[i][i] = 0;for ( int i = 0 ; i < n ; ++ i )visit[i] = 0;for ( int i = 0 ; i < n ; ++ i )Head[i] = NULL;Count = 0;
}
//插入边 
void addedge( int point1, int point2, int length )
{Edge[Count].point  = point2;Edge[Count].length = length;Edge[Count].next   = Head[point1];Head[point1] = &Edge[Count ++];
}
//邻接表 end //fibonacci_heap
typedef struct node_fib
{int       key,id;bool      mark;short     degree;node_fib* left;node_fib* right;node_fib* child;node_fib* father;
}fib_node;typedef struct node_arr
{short     degree;node_fib* addr;node_arr* next;
}arr_node;class fibonacci_heap
{private:fib_node* root;fib_node* base;fib_node**space;arr_node* array;arr_node**ahead;int       count;fib_node* newNode( int ID, int K );void Link( fib_node* q, fib_node* p );void Union( fib_node* r, fib_node* q );void Cut( fib_node* p );void Consolidate( fib_node* h );public:fibonacci_heap();void clear();bool empty( void ) {return (!root);}void Insert( int ID, int K );int  Delete( void );
}Heap;
fibonacci_heap::fibonacci_heap() {base  = new fib_node  [100];space = new fib_node* [100];array = new arr_node  [100];ahead = new arr_node* [100];clear();
}
void fibonacci_heap::clear() {root  = 0; count = 0;memset( base , 0, sizeof( fib_node  )*100 ); memset( space, 0, sizeof( fib_node* )*100 );memset( array, 0, sizeof( arr_node  )*100 ); memset( ahead, 0, sizeof( arr_node* )*100 );
} 
fib_node* fibonacci_heap::newNode( int ID, int K ) {fib_node* np = &base[ count ++ ];np->left = np->right = np;np->id = ID; np->key = K;space[ ID ] = np;return np;
}
void fibonacci_heap::Link( fib_node* q, fib_node* p ) {//p to qif ( !q->child ) q->child = p;else Union( q->child, p );p->father = q;q->degree ++ ;
}
void fibonacci_heap::Union( fib_node* r, fib_node* q ) {fib_node* p = q->right;p->left = r;q->right = r->right;r->right->left = q;r->right = p;
}
void fibonacci_heap::Cut( fib_node* p ) {if ( !p ) return;if ( p == root ) {root=NULL;return;}if ( p->father ) {p->father->degree --;if ( !p->father->mark ) p->father->mark = true;if ( p->father->child->left == p->father->child )p->father->child = NULL;else p->father->child = p->left;}fib_node* q = p->left;q->right = p->right;p->right->left = q;p->left = p->right = p;p->father = NULL;p->mark = false;
}
void fibonacci_heap::Insert( int ID, int K ) {if ( !space[ ID ] ) {fib_node* np = newNode( ID, K );if ( !root ) root = np;else {Union( root, np );if ( K < root->key ) root = np;}}else {fib_node* np = space[ ID ];fib_node* fp = NULL;if ( np->key < K ) return;np->key = K;if ( np->father && K < np->father->key ) {do {fp = np->father;Cut( np );if ( !root ) root = np;else Union( root, np );np = fp;}while ( np && np->mark && np != root );if ( np ) np->mark = true;//}if ( K < root->key ) root = space[ ID ];}
}
void fibonacci_heap::Consolidate( fib_node* h ) {int number = 0,maxdeg = 0,id = 0;if ( !h ) return;array[ number ].degree = maxdeg = h->degree;array[ number ].addr = h;for ( fib_node *p = h->left ; p != h ; p = p->left ) {++ number;array[ number ].degree = p->degree;array[ number ].addr = p;if ( maxdeg < p->degree ) maxdeg = p->degree;}if ( !number ) return;for ( int i = 0 ; i <= maxdeg ; ++ i )ahead[ i ] = NULL;for ( int i = 0 ; i <= number ; ++ i ) {id = array[ i ].degree;array[ i ].next = ahead[ id ];ahead[ id ] = &array[ i ];}arr_node *ap, *aq;for ( int i = 0 ; i <= maxdeg ; ++ i ) for ( ap = ahead[ i ] ; ap && ap->next ; ) {aq = ap->next;ahead[ i ] = aq->next;if ( !(ap->addr->key < aq->addr->key) && ap->addr != root )swap( ap->addr, aq->addr );Cut( aq->addr );Link( ap->addr, aq->addr );ap->next = ahead[ i+1 ];ahead[ i+1 ] = ap;ap = ahead[ i ];if ( i == maxdeg ) ahead[ ++ maxdeg ] = NULL;}
}
int fibonacci_heap::Delete( void ) {if ( !root ) return 0;fib_node* np = root->child;fib_node* fp = NULL;while ( np ) {fp = (np->left == np)?NULL:np->left;Cut( np );Union( root, np );np = fp;}fib_node* answer = root;root->child = NULL;root = root->left;if ( root != answer ) {Cut( answer );np = root;for ( fp = root->left ; fp != root ; fp = fp->left )if ( fp->key < np->key ) np = fp;root = np;Consolidate( root );}else root = NULL;return answer->id;
}
//fibonacci_heap endvoid dijkstra( int s, int n )
{Heap.clear();Heap.Insert( s, 0 );while ( !Heap.empty() ) {int now = Heap.Delete();for ( graph* p = Head[now] ; p ; p = p->next )if ( path[s][p->point] > path[s][now] + p->length ) {path[s][p->point] = path[s][now] + p->length;Heap.Insert( p->point, path[s][p->point] );}}
}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 );}//初始化距离，只计算可直达 initgraph( N );for ( int i = 0 ; i < M ; ++ i ) {scanf("%s%s",city1,city2);id1 = Hash.find( city1 );id2 = Hash.find( city2 );addedge( id1, id2, dist( lat[id1], lon[id1], lat[id2], lon[id2] ) );}//计算有向图多元最短路 for ( int i = 0 ; i < N ; ++ i )dijkstra( i, 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] == MAX_LENGTH )printf("no route exists\n");else printf("%d km\n",path[id1][id2]);}}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！