Walk Through the Forest UVA

Walk Through the Forest

题意：n个点，起点是1，终点是2，只能沿着满足条件的路走，如果走a-->b，那么存在一条从b到终点的路径，比从a到终点的路径都短，问有多少种方案。

先dijkstra处理1到各点的最短路d[i]，满足条件的路a-->b就是d[b]<d[a]的路径。

然后dp，dp[i]为从i到终点的方案数。

dp[u]=dp[u]+dp[v]，其中d[v]<d[u]。边界条件dp[终点]=1。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int inf=0x3f3f3f3f;
 4 const int maxv=1010;
 5 const int maxe=1000010; //??
 6 int n,m;
 7 struct Edge
 8 {
 9     int u,v,w;
10     int nex;
11 }e[maxe<<1];
12 int head[maxv];
13 int cnt=0;
14 void init()
15 {
16     memset(head,-1,sizeof(head));
17     cnt=0;
18 }
19 void add(int u,int v,int w)
20 {
21     e[cnt].u=u;
22     e[cnt].v=v;
23     e[cnt].w=w;
24     e[cnt].nex=head[u];
25     head[u]=cnt++;
26 }
27 typedef pair<int,int> PII;
28 int dis[maxv],par[maxv];
29 void dijkstra(int s)
30 {
31     priority_queue<PII,vector<PII>,greater<PII> > pq;
32     for(int i=0;i<maxv;i++) dis[i]=inf;
33     dis[s]=0;
34     pq.push(PII(0,s));
35     while(!pq.empty())
36     {
37         PII temp=pq.top();
38         pq.pop();
39         int u=temp.second;
40         if(dis[u]<temp.first) continue;
41         for(int i=head[u];i!=-1;i=e[i].nex)
42         {
43             int v=e[i].v;
44             if(dis[v]>dis[u]+e[i].w)
45             {
46                 dis[v]=dis[u]+e[i].w;
47                 par[v]=i;
48                 pq.push(PII(dis[v],v));
49             }
50         }
51     }
52 }
53 int dp[maxv];
54 int DP(int u)
55 {
56     if(u==1) return 1;
57     if(dp[u]!=-1) return dp[u];
58     dp[u]=0;
59     for(int i=head[u];i!=-1;i=e[i].nex)
60     {
61         int v=e[i].v;
62         if(dis[v]<dis[u]) dp[u]+=DP(v);
63     }
64     return dp[u];
65 }
66 int main()
67 {
68     while(scanf("%d",&n)&&n)
69     {
70         scanf("%d",&m);
71         init();
72         int u,v,w;
73         for(int i=0;i<m;i++)
74         {
75             scanf("%d%d%d",&u,&v,&w);
76             u--;v--;
77             add(u,v,w);
78             add(v,u,w);
79         }
80         dijkstra(1);
81         memset(dp,-1,sizeof(dp));
82         int ans=DP(0);
83         printf("%d
",ans);
84     }
85 
86 }

View Code