第一次的最短路经记录有问题？  代码如下：

#include <iostream>  //3068C
using namespace std;    //&sup3;&Igrave;&ETH;ò&para;&Ocirc;&Aacute;&Euml;  &micro;&laquo;&Ecirc;&Ccedil;&Euml;&atilde;·¨&micro;&Auml;&ETH;§&Acirc;&Ecirc;&Igrave;&laquo;&micro;&Iacute;&pound;&not;&sup3;&Igrave;&ETH;ò&Otilde;&ucirc;&Igrave;&aring;&frac12;á&sup1;&sup1;&iquest;&acute;&AElig;&eth;&Agrave;&acute;&Ograve;&sup2;&ordm;&Uuml;&sup2;&raquo;&ordm;&Atilde;

struct Edge
{
	_int64 i,j,c;
	bool used;
};
Edge ed[10000];
#define MAX 999999999
_int64 e,M,N;
_int64 cost[65][65];
_int64 use[65][65]; //&micro;&Uacute;&Ograve;&raquo;&acute;&Icirc;&Ntilde;&iexcl;&Ocirc;&ntilde;×&icirc;&Oacute;&Aring;&Ecirc;&AElig;&Ecirc;±i,j&Ocirc;&Uacute;M&Ouml;&ETH;&Euml;ù&Oacute;&Atilde;&micro;&Auml;

_int64 dp[65];//, num_dp;
bool final[65];
_int64 L[65],  rst;

void load1()  //&Oacute;&Eacute;&Oacute;&Uacute;&Atilde;&iquest;&Ouml;&Ouml;·&frac12;·¨&Ouml;&raquo;&Auml;&Uuml;&Oacute;&Atilde;&Ograve;&raquo;&acute;&Icirc;&pound;&not;&Euml;ù&Ograve;&Ocirc;&acute;&aelig;&Ocirc;&Uacute;&Iuml;&ucirc;&ordm;&Auml;&pound;&not;&ETH;è&Ograve;&ordf;&Aacute;&frac12;&acute;&Icirc;&frac14;&Ccedil;&Acirc;&frac14;
{   
	for(_int64 i=0;i<N;i++){
		for(_int64 j=0;j<N;j++){
			use[i][j] = -1;
		}
	}
    for(i=0;i<M;i++){
		if( ed[i].c<cost[ed[i].i][ed[i].j]){

			cost[ed[i].i][ed[i].j] = ed[i].c;
	        use[ed[i].i][ed[i].j] = i;
		}
	}
	for(i=0;i<N-1;i++){
		if( cost[0][0] < MAX )
			L[i] = 0;
		else
           L[i] = -1;
	} 
}
void load2()
{
       for(_int64 i=0;i<M;i++)
		if(!ed[i].used && ed[i].c<cost[ed[i].i][ed[i].j])
           cost[ed[i].i][ed[i].j] = ed[i].c;

}
void Diskstra()
{
    _int64 i,j,p,min ;
	for(i=0;i<N;i++){
		final[i] = false; dp[i] = cost[0][i]; 
	}
    final[0] = true;

	for(i=1; i<N;i++){   //&Ouml;÷&Ntilde;&shy;&raquo;·
       min = MAX;  p=-1;
	   for( j= 0 ; j<N;j++) { //&Ntilde;°&Otilde;&Ograve;&acute;&Icirc;&para;&Igrave;&Acirc;·&frac34;&para;, &Oacute;&ETH;&Otilde;&Ograve;&sup2;&raquo;&micro;&frac12;&micro;&Auml;&iquest;&Eacute;&Auml;&Uuml;&ETH;&Ocirc;&Auml;&Oslash;
		   if(!final[j] )
			   if( dp[j] <  min)    {p = j; min = dp[j];}
	   }
	   if(p==-1)  //&Atilde;&raquo;&Otilde;&Ograve;&micro;&frac12;&pound;&not;·&micro;&raquo;&Oslash;×&icirc;&para;&Igrave;&Acirc;·&frac34;&para;
	   {
		   rst = MAX; return;
	   }
	   final[p] = true;
	   if(p == N-1) 
		   break;
	   for(j=0; j<N;j++)  //&cedil;ú&ETH;&Acirc;
	       if( !final[j] && (min+cost[p][j] < dp[j]  ) ) {
			   dp[j] = min+cost[p][j] ; 
			   L[j] = p;   //&frac14;&Ccedil;&Acirc;&frac14;&Auml;&Auml;&Ograve;&raquo;&cedil;&ouml;&para;¨&micro;&atilde;&Euml;&cent;&ETH;&Acirc;&Aacute;&Euml;×&Ocirc;&frac14;&ordm;&micro;&Auml;&Acirc;·&frac34;&para;&sup3;¤&para;&Egrave;
		   }
	}
	rst +=dp[N-1];
}
void work(_int64 th)
{
	rst =0;
    printf("Instance #%I64d: ",th);
    _int64 i,j;
    for(i=0;i<M;i++)   //±&Oslash;&ETH;&euml;
		 ed[i].used = false;

    for(i=0;i<N;i++){  //±&Oslash;&ETH;&euml;
		for(j=0;j<N;j++)
			cost[i][j] =MAX; 
		cost[i][i] = 0;
	}   load1();
	
	Diskstra();
    if(rst >=MAX)  {printf("Not possible\n"); return;}
	i = N-1;
	while(true){   
		ed[ use[L[i]][i] ].used  =true;
		i = L[i];
		if(i==0)
			break;
	}

	for(i=0;i<N;i++){  //±&Oslash;&ETH;&euml;
		for(j=0;j<N;j++)
			cost[i][j] =MAX; 
		cost[i][i] = 0;
	}   load2();
 
	Diskstra(); 
	if(rst >=MAX)  {printf("Not possible\n"); return;}
    
	printf("%I64d\n",rst);
}

_int64 main()
{
    scanf("%d%d",&N,&M);
	_int64 p; _int64 th=1;
	while(N!=0 && M!=0){
        p=0; 
		while(p<M){
			scanf("%d%d%d",&ed[p].i,&ed[p].j,&ed[p].c); 
			p++; 
		}
		work(th);
		th++;
        scanf("%d%d",&N,&M);
	} 
	return 0;
}

• 让第一个路径最短，再让第二个最短，不能保证两个加起来最短 (4025) bmexue 2006-11-10 16:40:19