单页网站制作视频教程,四川餐饮培训学校排名,登烈建站,王也天个人资料http://acm.hdu.edu.cn/showproblem.php?pid1142 题意#xff1a; Jimmy在位置 1 #xff0c;每天晚上要回位置2#xff08;家#xff09;#xff0c;计算1到2的最短距离#xff0c;Jimmy要先去一个地方然后再回家#xff0c;到了那个地方离家的距离不能大于1到2 的最短…http://acm.hdu.edu.cn/showproblem.php?pid1142 题意 Jimmy在位置 1 每天晚上要回位置2家计算1到2的最短距离Jimmy要先去一个地方然后再回家到了那个地方离家的距离不能大于1到2 的最短距离计算出有多少种这样的走法。 坑爹 当用DFS搜索有多少条路径时会超时。 解法 剪枝用mark数组记录上一次走到这一个点在往下走有多少条路径时符合条件的。 View Code 1 #includeiostream2 using namespace std;3 4 const int MAXN 1000 10 ;5 const int MAX 1000000 10 ;6 7 int N;8 int M;9 int dis[MAXN] ;
10 int map[MAXN][MAXN];
11 int used[MAXN];
12 int mark[MAXN]; // 某点到家的符合条件的路径有多少种
13 int flag[MAXN];
14
15 void dijskra(int x)
16 {
17 dis[x] 0 ;
18 used[x] 0;
19
20 for(int j 0 ; j N ; j )
21 {
22 int mix MAX;
23 int y;
24
25 for( int i 1 ; i N ; i )
26 {
27 if( !used[i] dis[i] mix )
28 {
29 mix dis[i] ;
30 y i ;
31 }
32 }
33
34 used[y] 1;
35
36
37 for( i 1 ; i N ;i )
38 {
39 if(!used[i])
40 {
41 if( dis[i] dis[y] map[y][i] map[y][i] )
42 {
43 dis[i] dis[y] map[y][i] ;
44 }
45 }
46 }
47 }
48 }
49
50 int DFS(int x)
51 {
52 if(x 2)
53 {
54 return 1;
55 }
56
57 if(mark[x] ! 0 )
58 {
59 return mark[x];
60 }
61
62 for( int i 1 ; i N ; i )
63 {
64 if(dis[i] dis[x] !flag[i] map[x][i] )
65 {
66 mark[x] DFS(i);
67 }
68 }
69 return mark[x];
70 }
71
72
73
74 int main()
75 {
76 while(cin N , N )
77 {
78 cin M ;
79 memset( map , 0 , sizeof(map)) ;
80 memset( used , 0 , sizeof(used)) ;
81 memset( dis , MAX, sizeof(dis)) ;
82 memset( mark , 0 , sizeof(mark)) ;
83 memset( flag , 0 , sizeof(flag)) ;
84
85 for(int i 0 ; i M ; i )
86 {
87 int a;
88 int b;
89 int c;
90 cin a b c ;
91 map[a][b] c ;
92 map[b][a] c ;
93 }
94
95 dijskra(2);
96 coutDFS(1)endl;
97 }
98 return 0;
99 } 转载于:https://www.cnblogs.com/pcpcpc/archive/2012/09/03/2669377.html
