首页 > 代码库 > HDU 1142 A Walk Through the Forest(dijkstra+记忆化DFS)

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

2024-07-13 20:23:46   225人阅读

题意：

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

思路：

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

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

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

AC_CODE:

 1 #include<stdio.h> 2 #include<string.h> 3 #define INF 10000000 4 int map[1001][1001]; 5 int vis[1001]; 6 int dis[1001]; 7 int n,m; 8 int dp[1001]; 9 void dijkstra(int st)10 {11     int i,j,k;12     memset(vis,0,sizeof(vis));13     for(i=1;i<=n;i++)14     {15         if(i==st)16             dis[i]=0;17         else18             dis[i]=INF;19     }20     for(i=1;i<=n;i++)21     {22         int r;23         int min=INF;24         for(j=1;j<=n;j++)25         {26             if(!vis[j]&&dis[j]<min)27             {28                 min=dis[j];29                 r=j;30             }31         }32         vis[r]=1;33         for(k=1;k<=n;k++)34         {35             if(dis[k]>dis[r]+map[r][k])36                 dis[k]=dis[r]+map[r][k];37         }38     }39     return;40 }41 int DFS(int st)42 {43     int sum=0;44     if(dp[st]!=-1)45         return dp[st];46     if(st==2)47         return 1;48     for(int i=1;i<=n;i++)49     {50         if(map[st][i]!=INF&&dis[st]>dis[i])51             sum+=DFS(i);52     }53     dp[st]=sum;54     return dp[st];55 }56 int main()57 {58     int i,j,u,v,w;59     while(scanf("%d",&n)!=EOF&&n)60     {61         for(i=1;i<=n;i++)62         {63             dp[i]=-1;64             for(j=1;j<=n;j++)65             {66                 if(i==j)67                     map[i][j]=0;68                 else69                     map[i][j]=INF;70             }71         }72         scanf("%d",&m);73         for(i=1;i<=m;i++)74         {75             scanf("%d%d%d",&u,&v,&w);76             map[u][v]=map[v][u]=w;77         }78         dijkstra(2);79         printf("%d\n",DFS(1));80     }81     return 0;82 }

                                                                                                                                    ————Anonymous.PJQ

    


联系
我们