spfa.rar_SPFA

#define Max 10000002 #define NodeSize 111 #define QueuSize 1002 #include<iostream> #include<stdlib.h> using namespace std; struct Node { int Point; int Dista; Node *Next; }; Node* Head[ NodeSize ]; /* 邻接表的头指针 */ void FreeHead( int Nodesize ) { for ( int i = 1 ; i <= Nodesize ; ++ i ) { Node * freePoint = Head[ i ]; if ( !freePoint ) continue; for ( Node* P = Head[ i ] ; P ; ) { freePoint = P; P = P->Next; free( freePoint ); } } } void MadeList( int Nodesize , int Pathsize ) { /*创建邻接表*/ Node *Mery[ NodeSize ]; /* 记录当前节点 */ for ( int i = 1 ; i <= Nodesize ; ++ i ) { Head[ i ] = NULL; Mery[ i ] = NULL; } int Point1,Point2,Path; for ( int i = 1 ; i <= Pathsize ; ++ i ) { cin >> Point1 >> Point2 >> Path; /* 单向邻接表 */ if ( !Head[ Point1 ] ) { Head[ Point1 ] = ( Node* )malloc( sizeof( Node ) ); Head[ Point1 ]->Point = Point2; Head[ Point1 ]->Dista = Path; Head[ Point1 ]->Next = NULL; Mery[ Point1 ] = Head[ Point1 ]; } else { Mery[ Point1 ]->Next = ( Node* )malloc( sizeof( Node ) ); Mery[ Point1 ] = Mery[ Point1 ]->Next; Mery[ Point1 ]->Point = Point2; Mery[ Point1 ]->Dista = Path; Mery[ Point1 ]->Next = NULL; } /* 双向邻接表 */ if ( !Head[ Point2 ] ) { Head[ Point2 ] = ( Node* )malloc( sizeof( Node ) ); Head[ Point2 ]->Point = Point1; Head[ Point2 ]->Dista = Path; Head[ Point2 ]->Next = NULL; Mery[ Point2 ] = Head[ Point2 ]; } else { Mery[ Point2 ]->Next = ( Node* )malloc( sizeof( Node ) ); Mery[ Point2 ] = Mery[ Point2 ]->Next; Mery[ Point2 ]->Point = Point1; Mery[ Point2 ]->Dista = Path; Mery[ Point2 ]->Next = NULL; } } } int SPFA( int Nodesize , int EndPoint ) { int Queu[ QueuSize ]; /*记录被优化的节点*/ int Dist[ NodeSize ]; /*记录最短路径长度*/ int Sign[ NodeSize ]; /*记录队列中的节点*/ int Count = 1; int Save = 0; int Move = 0; for ( int i = 1 ; i <= Nodesize ; ++ i ) { Sign[ i ] = 0; Dist[ i ] = Max; } Dist[ EndPoint ] = 0; Sign[ EndPoint ] = 1; Queu[ Save ++ ] = EndPoint; while ( Count ) { for ( Node* P = Head[ Queu[ Move ] ] ; P ; P = P->Next ) { if ( P->Dista > 0 && Dist[ P->Point ] > P->Dista + Dist[ Queu[ Move ] ] ) { Dist[ P->Point ] = P->Dista + Dist[ Queu[ Move ] ]; if ( !Sign[ P->Point ] ) { Queu[ Save ++ ] = P->Point; Sign[ P->Point ] = 1; ++ Count; } } } Sign[ Queu[ Move ++ ] ] = 0; -- Count; } return Dist[ Nodesize ]; } int main() { int N,M; while ( cin >> N >> M && N ) { MadeList( N , M ); cout << SPFA( N ,1 ) << "\n"; FreeHead( N ); } system("pause"); }