UVA 10917 Walk Through the Forest（dijkstra+DAG上的dp）

用新模板阿姨了一天，换成原来的一遍就ac了= =

题意很重要。。最关键的一句话是说:若走A->B这条边，必然是d[B]<d[A]，d[]数组保存的是各点到终点的最短路。

所以先做dij，由d[B]<d[A]可知，所走的路径上各点的d[]值是由大到小的，即是一个DAG，从而决定用记忆化搜索查找总的路径数。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int MAXN=1111;
 7 const int INF =0x0fffff;
 8 
 9 int G[MAXN][MAXN],vis[MAXN],d[MAXN],n;
10 int mark[MAXN],dp[MAXN];
11 
12 void dij(int n)
13 {
14     memset(vis,0,sizeof(vis));
15     for(int i=1;i<=n;i++)
16         if(i==2)d[i]=0;
17         else d[i]=INF;
18     for(int i=0;i<n;i++)
19     {
20         int x,m=INF;
21         for(int y=1;y<=n;y++)
22         if(!vis[y]&&d[y]<m){
23             x=y;
24             m=d[x];
25         }
26         vis[x]=1;
27         for(int y=1;y<=n;y++)
28             if(d[y]>d[x]+G[x][y])
29                 d[y]=d[x]+G[x][y];
30     }
31 }
32 
33 int dfs(int u,int ed)
34 {
35     if(mark[u])
36         return dp[u];
37     mark[u]=1;
38     if(u==ed){
39         dp[u]=1;
40         return dp[u];
41     }
42     int ans=0;
43     for(int i=1;i<=n;i++)
44     {
45         if(G[u][i]!=INF&&d[i]<d[u])
46             ans+=dfs(i,ed);
47     }
48     dp[u]=ans;
49     return dp[u];
50 }
51 
52 int main()
53 {
54     int m,u,v,c;
55     while(~scanf("%d",&n))
56     {
57         if(!n)
58             return 0;
59         scanf("%d",&m);
60         for(int i=1;i<=n;i++)
61             for(int j=1;j<=n;j++)
62                 if(i==j)G[i][j]=0;
63                 else G[i][j]=INF;
64         for(int i=0;i<m;i++)
65         {
66             scanf("%d%d%d",&u,&v,&c);
67             if(G[u][v]>c)
68                 G[u][v]=G[v][u]=c;
69         }
70 
71         dij(n);
72 
73         memset(mark,0,sizeof(mark));
74         printf("%d
",dfs(1,2));
75 
76     }
77     return 0;
78 }

View Code

后记：

回顾这道题，想到了一个问题：两点之间可以存在重边，用邻接表存储，同一条路线会被重复计算。e.g：1->2->3，即d[1]>d[2]>d[3]，如果1->2有两条路，那么这两条路都符合d[1]>d[2]的条件。虽然题目中描述Jimmy想从不同的路线经过，而事实上应该是不算重边的。