uva 10917 Walk Through The Forest

题意：

一个人从公司回家，他可以从A走到B如果从存在从B出发到家的一条路径的长度小于任何一条从A出发到家的路径的长度。

问这样的路径有多少条。

思路：

题意并不好理解，存在从B出发到家的一条路径的长度小于任何一条从A出发到家的路径的长度，从这个条件可以推出只要满足B到家的最短路小于从A到家的最短路，那么就是满足条件的。

所以从家开始求到各个点的最短路，然后从公司开始进行记忆化搜索求出路径的总条数。

如果两个点A和B满足d[A] > d[B]，那么A到家的路径条数一定包括B到家的路径条数，临界条件就是到家了，那么只有一条路可以走。

复杂度O(nlog(n));

代码：

  1 #include <stdio.h>
  2 #include <vector>
  3 #include <queue>
  4 #include <string.h>
  5 using namespace  std;
  6 
  7 struct edge
  8 {
  9     int to;
 10     long long cost;
 11     
 12     edge(int uu,long long vv)
 13     {
 14         to = uu;
 15         cost  = vv;
 16     }
 17 };
 18 
 19 const int maxn = 1005;
 20 
 21 vector<edge> g[maxn];
 22 long long d[maxn];
 23 bool vis[maxn];
 24 long long dp[maxn];
 25 
 26 void adde(int st,int to,int cost)
 27 {
 28     g[st].push_back(edge(to,cost));
 29 }
 30 
 31 void dij(int s,int n)
 32 {
 33     for (int i = 0;i <= n;i++) d[i] = 10000000000000000;
 34     memset(vis,0,sizeof(vis));
 35     
 36     d[s] = 0;
 37     
 38     for (int i = 0;i < n - 1;i++)
 39     {
 40         long long dis = 10000000000000000;
 41         int x;
 42         
 43         for (int j = 1;j <= n;j++)
 44         {
 45             if (d[j] <= dis && !vis[j])
 46             {
 47                 dis = d[j];
 48                 x = j;
 49             }
 50         }
 51         
 52         vis[x] = 1;
 53         
 54         for (int j = 0;j < g[x].size();j++)
 55         {
 56             edge e = g[x][j];
 57             
 58             if (d[e.to] > d[x] + e.cost)
 59             {
 60                 //ways[e.to] = ways[x];
 61                 d[e.to] = d[x] + e.cost;
 62             }
 63         }
 64     }
 65 }
 66 
 67 int dfs(int u,int fa)
 68 {
 69     if (dp[u] != -1) return dp[u];
 70     
 71     dp[u] = 0;
 72     
 73     for (int i = 0;i < g[u].size();i++)
 74     {
 75         int v = g[u][i].to;
 76         
 77         if (v == fa) continue;
 78         
 79         if (d[u] > d[v])
 80         {
 81             if (dp[v] != -1) dp[u] += dp[v];
 82             else dp[u] += dfs(v,u);
 83         }
 84     }
 85     
 86     return dp[u];
 87 }
 88 
 89 int main()
 90 {
 91     int n,m;
 92     
 93     while (scanf("%d",&n) != EOF)
 94     {
 95         if (n == 0) break;
 96         
 97         scanf("%d",&m);
 98         
 99         for (int i = 0;i <= n;i++) g[i].clear();
100         memset(dp,-1,sizeof(dp));
101         
102         //memset(ways,0,sizeof(ways));
103         
104         for (int i = 0;i < m;i++)
105         {
106             int x,y,z;
107             
108             scanf("%d%d%d",&x,&y,&z);
109             
110             adde(x,y,z);
111             adde(y,x,z);
112         }
113         
114         dij(2,n);
115         
116         //memset(vis,0,sizeof(vis));
117         
118         dp[2] = 1;
119         
120         dfs(1,-1);
121         
122         printf("%lld
",dp[1]);
123     }
124     
125     return 0;
126 }