#include<iostream.h>
//#include<fstream.h>

int t,n;//T and N

class node
{
public:
	int w;
	int to;
	node * next;
};


node * array[1000];
 
node * p;
int length;

void main()
{
	length=0;
//	fstream in("in.txt",ios::in|ios::out);
	cin>>t>>n;
	int	r[1001][2];//r[i][0]==r[i].to  r[i][1]==r[i].w
	int i,j,temp;
	int f,to,w;

	for(i=1;i<=t;i++)//input 
	{
		cin>>f>>to>>w;
		p=new node;
		p->w=w;
		p->to=to;
		p->next=array[f];
		array[f]=p;
		p=NULL;
	}

//	in.close();

	i=1;

	r[0][0]=0;//store the numbers of the record in r[]
	while(1)
	{

		for(p=array[i];p!=NULL;p=p->next)		//update()
		{
				j=r[0][0]+1;					//store record between 1 to n 
				w=p->w+length;					//new weight from 1 to p.to
				for(i=1;i<=r[0][0];i++)
				{

					if(p->to==r[i][0])
					{
						j=i;
						if(w<r[i][1])
						{
							r[i][1]=w;
							if(p->to==n)
							{
								cout<<w<<endl;
								return;
							}
						}
						break;
					}
						
				}//end for
				if(j==r[0][0]+1)
				{
					r[j][0]=p->to;
					r[j][1]=w;
					r[0][0]++;
				}		
				
		}

		temp=1;		
		for(j=2;j<=r[0][0];j++)
		{
			// search the min
			if(r[temp][1]>r[j][1])
				temp=j;		
		}										//end search

		length=r[temp][1];
		i=r[temp][0];
		r[i+1][1]=r[r[0][0]][1];

		r[0][0]--;

		if(i==n)
			break;
	}	
 	///////////end process

	cout<<length<<endl;

}

• Re:超了15ms。不知道怎么办了？帮忙看看吧 (42) dfitf 2005-04-09 14:25:33
• Re:说得对 (1634) fxlbest 2005-10-29 12:31:27