#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");
}
评论0