> 第一次的最短路经记录有问题？  代码如下：
> 
> #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;
> }