poj 2662(Dijkstra+记忆化)

题目链接：http://poj.org/problem?id=2662

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<vector>

 using namespace std;

 #define MAXN 1111

 #define inf 1<<30

 struct Edge{

     int v,w;

     Edge(int vv,int ww):v(vv),w(ww){}

 };

 int n,m;

 int dist[MAXN];

 bool mark[MAXN];

 int dp[MAXN];

 vector<vector<Edge> >G;

 void Dijkstra(int st)

 {

     memset(mark,false,sizeof(mark));

     fill(dist,dist+n+,inf);

     dist[st]=;

     priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >que;

     que.push(make_pair(,st));

     while(!que.empty()){

         int u=que.top().second,dd=que.top().first;

         que.pop();

         if(mark[u])continue;

         mark[u]=true;

         for(int i=;i<G[u].size();i++){

             int v=G[u][i].v,w=G[u][i].w;

             if(mark[v])continue;

             if(dd+w<dist[v]){

                 dist[v]=dd+w;

                 que.push(make_pair(dist[v],v));

             }

         }

     }

 }

 int dfs(int u)

 {

     if(u==)return ;

     if(dp[u])return dp[u];

     for(int i=;i<G[u].size();i++){

         int v=G[u][i].v,w=G[u][i].w;

         if(dist[v]<dist[u]){

             dp[u]+=dfs(v);

         }

     }

     return dp[u];

 }

 int main()

 {

     int u,v,w;

     while(~scanf("%d",&n)&&n){

         scanf("%d",&m);

         G.clear();

         G.resize(n+);

         while(m--){

             scanf("%d%d%d",&u,&v,&w);

             G[u].push_back(Edge(v,w));

             G[v].push_back(Edge(u,w));

         }

         Dijkstra();

         memset(dp,,sizeof(dp));

         printf("%d\n",dfs());

     }

     return ;

 }