/* simply using Dijkastra*/ 
#include <iostream>
#include <cstring>
using namespace std;

const int MAXSIZE=1010;
const int MAXINT=5000;
typedef struct
{
	int next,dist;
}NextPoint;

int landMark[MAXSIZE][MAXSIZE]={0};//describe distance bettween land marks
int close[MAXSIZE];// points to choose from
bool marked[MAXSIZE]={false};// points already included
int N,T;

void Input()
{
	cin>>N>>T;
	int i,j;	
	
	while (T--)
	{
		cin>>i>>j;
		cin>>landMark[i][j];
		landMark[j][i]=landMark[i][j];
	}
/*	for (i=1;i<=N;i++)
	{
		for (j=1;j<=N;j++)
			cout<<landMark[i][j]<<' ';
		cout<<endl;
	}*/
}

void FindClose(NextPoint &p)
{
	int i;
	int closestDist=MAXINT,closestPoint;

	for (i=1;i<=N;i++)
	{
		if (!marked[i]&&close[i]!=0&&close[i]<closestDist)
		{
			closestDist=close[i];
			closestPoint=i;
		}
	}
//	cout<<"Dis & add:"<<closestDist<<' '<<closestPoint<<endl;
	p.dist=closestDist;
	p.next=closestPoint;
}

void UpdateDist(NextPoint &p)
{
	int i;
	for (i=1;i<=N;++i)
	{
		if (!marked[i]&&landMark[p.next][i]!=0&&(p.dist+landMark[p.next][i]<close[i]||close[i]==0))
		{
			close[i]=p.dist+landMark[p.next][i];
		}
	}
}


int main()
{
	Input();
	int i;
	for (i=1;i<=N;i++)
	{
			close[i]=landMark[N][i];
	}
	NextPoint p;
	marked[N]=true;  //added start point

	while (1)
	{
		FindClose(p);
		marked[p.next]=true;
		if (marked[1])
			break;
		UpdateDist(p);
	}
	cout<<p.dist<<endl;
	return 0;
}

• Re:为什么是Run time error? (796) vikeydr 2008-07-19 13:36:49
• Re:为什么是Run time error? (1724) Epsilon1205 2009-02-24 01:19:47