http://acm.hdu.edu.cn/showproblem.php?pid=2544

hdu2544 

#include 

#define mx 99999

using namespace std;

int edge[103][103] ;

int n , m , a, b ,c ;

void floyd()
{
  for(int k = 1 ; k <= n; k ++)
   for(int i = 1; i <= n; i ++)
    for(int j = 1; j <= n; j ++)
     if(edge[i][j] > edge[i][k] + edge[k][j])
  {
   edge[i][j] = edge[i][k] + edge[k][j] ;
  }
}
int main()
{
  while(cin >> n >> m)
  {
   if(!n && !m) break ;

   for(int i = 1; i <= n; i ++)
   {
    for(int j = 1; j <= n; j ++)
     edge[i][j] = mx;
   }
   for(int i = 0; i < m; i ++)
   {
    cin >> a >> b >> c ;
    if(edge[a][b] == mx)
     edge[a][b] = edge[b][a] = c;
    else if(edge[a][b] > c)
    {
     edge[a][b] = edge[b][a] = c ;
    }
   }
   floyd() ;
   cout << edge[1][n] << endl;
  }
 return 0 ;
}

 floyd   ，        。      。