poj 2662(Dijkstra+记忆化)

思路：首先路径的选择，如果B点到终点的距离比A点到终点的最短距离短，那么就从A走到B,换句话说，就是每次都是择优选择更靠近终点的点。于是我们可以从终点2跑一次Dijkstra，求出每个点到终点的最短距离，然后就是从起点1开始记忆化搜索，如果满足上面条件的，就dfs.

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<vector>
 7 using namespace std;
 8 #define MAXN 1111
 9 #define inf 1<<30
10 
11 struct Edge{
12     int v,w;
13     Edge(int vv,int ww):v(vv),w(ww){}
14 };
15 
16 int n,m;
17 int dist[MAXN];
18 bool mark[MAXN];
19 int dp[MAXN];
20 
21 vector<vector<Edge> >G;
22 void Dijkstra(int st)
23 {
24     memset(mark,false,sizeof(mark));
25     fill(dist,dist+n+1,inf);
26     dist[st]=0;
27     priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >que;
28     que.push(make_pair(0,st));
29     while(!que.empty()){
30         int u=que.top().second,dd=que.top().first;
31         que.pop();
32         if(mark[u])continue;
33         mark[u]=true;
34         for(int i=0;i<G[u].size();i++){
35             int v=G[u][i].v,w=G[u][i].w;
36             if(mark[v])continue;
37             if(dd+w<dist[v]){
38                 dist[v]=dd+w;
39                 que.push(make_pair(dist[v],v));
40             }
41         }
42     }
43 }
44 
45 int dfs(int u)
46 {
47     if(u==2)return 1;
48     if(dp[u])return dp[u];
49     for(int i=0;i<G[u].size();i++){
50         int v=G[u][i].v,w=G[u][i].w;
51         if(dist[v]<dist[u]){
52             dp[u]+=dfs(v);
53         }
54     }
55     return dp[u];
56 }
57 
58 int main()
59 {
60     int u,v,w;
61     while(~scanf("%d",&n)&&n){
62         scanf("%d",&m);
63         G.clear();
64         G.resize(n+2);
65         while(m--){
66             scanf("%d%d%d",&u,&v,&w);
67             G[u].push_back(Edge(v,w));
68             G[v].push_back(Edge(u,w));
69         }
70         Dijkstra(2);
71         memset(dp,0,sizeof(dp));
72         printf("%d
",dfs(1));
73     }
74     return 0;
75 }

View Code