HDU 1142 A Walk Through the Forest(dijkstra+记忆化DFS)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：

给你一个图，找最短路。但是有个非一般的的条件：如果a,b之间有路，且你选择要走这条路，那么必须保证a到终点的所有路都小于b到终点的一条路。问满足这样的路径条数有多少，噶呜~~题意是搜了解题报告才明白的Orz.。。。英语渣~

思路：

1.1为起点，2为终点，因为要走ab路时，必须保证那个条件，所以从 终点开始使用单源最短路Dijkstra算法，得到每个点到终点的最短路，保存在dis[]数组中 。

2.然后从起点开始深搜每条路，看看满足题意的路径有多少条。

3.这样搜索之后，dp[1]就是从起点到终点所有满足题意的路径的条数。

AC_CODE:

 #include<stdio.h>

 #include<string.h>

 #define INF 10000000

 int map[][];

 int vis[];

 int dis[];

 int n,m;

 int dp[];

 void dijkstra(int st)

 {

     int i,j,k;

     memset(vis,,sizeof(vis));

     for(i=;i<=n;i++)

     {

         if(i==st)

             dis[i]=;

         else

             dis[i]=INF;

     }

     for(i=;i<=n;i++)

     {

         int r;

         int min=INF;

         for(j=;j<=n;j++)

         {

             if(!vis[j]&&dis[j]<min)

             {

                 min=dis[j];

                 r=j;

             }

         }

         vis[r]=;

         for(k=;k<=n;k++)

         {

             if(dis[k]>dis[r]+map[r][k])

                 dis[k]=dis[r]+map[r][k];

         }

     }

     return;

 }

 int DFS(int st)

 {

     int sum=;

     if(dp[st]!=-)

         return dp[st];

     if(st==)

         return ;

     for(int i=;i<=n;i++)

     {

         if(map[st][i]!=INF&&dis[st]>dis[i])

             sum+=DFS(i);

     }

     dp[st]=sum;

     return dp[st];

 }

 int main()

 {

     int i,j,u,v,w;

     while(scanf("%d",&n)!=EOF&&n)

     {

         for(i=;i<=n;i++)

         {

             dp[i]=-;

             for(j=;j<=n;j++)

             {

                 if(i==j)

                     map[i][j]=;

                 else

                     map[i][j]=INF;

             }

         }

         scanf("%d",&m);

         for(i=;i<=m;i++)

         {

             scanf("%d%d%d",&u,&v,&w);

             map[u][v]=map[v][u]=w;

         }

         dijkstra();

         printf("%d\n",DFS());

     }

     return ;

 }