首页 > 其他 > 详细

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

时间:2014-07-24 22:06:22      阅读:160      评论:0      收藏:0      [点我收藏+]

题意:

    给你一个图,找最短路。但是有个非一般的的条件:如果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         else
18             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                 else
69                     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

    

HDU 1142 A Walk Through the Forest(dijkstra+记忆化DFS),布布扣,bubuko.com

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

原文:http://www.cnblogs.com/PJQOOO/p/3866182.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!