学步园

#include<stdio.h>
#include<stdlib.h>
int m,n,map[1024][1024],des[1024],dis[1024],dep[1024];
int inf = 0x7fffffff;
int Dijkstra( int p )
{
    dis[p] = 0;
    for( int i = 1; i <= n; ++i )
    {
         int min = inf, pos = 0,t;
         for( int j = 1; j <= n; ++j )
         {
              if( !des[j] )
                  if( dis[j] < min )
                  {
                      min = dis[j];
                      pos = j;
                  }
          }
          des[pos] = 1;
          for( int j = 1; j <= n; ++j )
          {
               if( !des[j] )
                   if( map[pos][j] != inf )
                       if( ( t = map[pos][j] + dis[pos] ) < dis[j] )
                           dis[j] = t;
           }
     }
     return 0;
}
int DFS( int x )
{
    
    if( dep[x] )//记忆化搜索
        return dep[x];
    if( x == 2 )
        return 1;
    for( int i = 1; i <= n ; ++i )
    {
         if( map[x][i] != inf )
             if( dis[i] < dis[x] )
                 dep[x] += DFS( i );
     }
     return dep[x];
}
int main( )
{
    while( scanf( "%d",&n ),n )
    {
           
           scanf( "%d",&m );
           for( int i = 0; i <= n; ++i )
           {
                for( int j = 0; j <= n; ++j )
                     map[i][j] = inf;
                des[i] = 0;
                dis[i] = inf;
                dep[i] = 0;
            }
            for( int i = 1; i <= m; ++i )
            {
                 int x,y,v;
                 scanf( "%d%d%d",&x,&y,&v );
                 map[x][y] = map[y][x] = v;
             }
            Dijkstra( 2 );
            int res = DFS( 1 );
            printf( "%d\n",res );
           }
          // system ("pause");
    return 0;
}

此题题意很容易理解错误，开始一直没能正确理解，我们一群人理解了好久才理解过来，解题思路，先把所有的点到2连通起来，并且算出最短路（Dijkstra），然后再使用深度搜索（DFS），找出比A到B短的路，怎么找比A到B短的路呢？方法如下：每次深度搜索都找出比递归传进来的参数到2的距离短的点这样一直递归下去，就能找出比A到B短的路的方法，还有DFS比较容易超时，这里要用记忆化搜索