学步园

Bellman-ford 算法

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

int mp[210][210];
int dis[210];
int N, M;
const int inf = 0x7f7f7f7f;

void bellman_ford( )
{
   //初始话
   for( int i = 1; i <= N; i++)
   {
       dis[i] = inf;     
        
   }
   dis[1] = 0;
   for( int i = 1; i < N; i++)
   {
        
      for( int j = 1; j <= N; j++)
        for( int k = 1; k <= N; k++) 
        {
           if( dis[k] > dis[j] + mp[j][k]  && mp[j][k] != inf)   
             dis[k] = dis[j] + mp[j][k];
        }
        
        
   }     
   printf("%d\n", dis[N]);
}

int main( )
{
  int a, b, c;
  while ( scanf("%d%d", &N, &M ), N + M)
  {
     for( int i = 1; i <= N; i++)
          for( int j = 1; j <= N; j++)
          {
               mp[i][j] = ( i == j ) ? 0 : inf;
               dis[j] = inf;
          }
     for( int i = 1;  i <= M; i++)
     {
        scanf("%d%d%d",&a,&b,&c);
        mp[a][b] = mp[b][a] = min( mp[a][b], c);     
          
     }    
     bellman_ford( );  
        
  }
  
}