设为首页 加入收藏

TOP

UVA 10917 Walk Through the Forest（Dijkstra+DAG动态规划）
2015-07-24 05:00:10 来源: 作者: 【大 中 小】 浏览:5次
Tags：UVA 10917 Walk Through the Forest Dijkstra DAG 动态 规划

题意：gbn最近打算穿过一个森林，但是他比较傲娇，于是他决定只走一些特殊的道路，他打算只沿着满足如下条件的（A,B）道路走：存在一条从B出发回家的路，比所有从A出发回家的路径都短。你的任务是计算一共有多少条不同的回家路径。其中起点的编号为1，终点的编号为2.

思路：首先从终点Dijkstra一次，求出每个点u回家的最短路长度，那么相当于创建了一个新图，当d[B]

?

#include
  
     
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
          #include
          
            #include
           
             #include
            
              #include
              #include
              
                #define eps 1e-6 #define LL long long using namespace std; const int maxn = 1000 + 5; const int INF = 100000000; int n, m; //Dijkstra struct Edge { int from, to, dist; Edge(int u = 0, int v = 0, int d = 0) : from(u), to(v), dist(d) { } }; struct HeapNode { ///用到的优先队列的结点 int d, u; bool operator < (const HeapNode& rhs) const { return d > rhs.d; } }; struct Dijkstra { int n, m; //点数和边数 vector
               
                 edges; //边列表 vector
                
                  G[maxn]; //每个节点出发的边编号 bool done[maxn]; //是否已经永久编号 int d[maxn]; //s到各个点的距离 int p[maxn]; //最短路中的上一条边 LL dp[maxn]; void init(int n) { this->n = n; for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); memset(dp, -1, sizeof(dp)); } void AddEdge(int from, int to, int dist) { //如果是无向图需要调用两次 edges.push_back(Edge(from, to, dist)); m = edges.size(); G[from].push_back(m-1); } void dijkstra(int s) { //求s到所有点的距离 priority_queue
                 
                   Q; for(int i = 0; i < n; i++) d[i] = INF; d[s] = 0; memset(done, 0, sizeof(done)); Q.push((HeapNode){0, s}); while(!Q.empty()) { HeapNode x = Q.top(); Q.pop(); int u = x.u; if(done[u]) continue; done[u] = true; for(int i = 0; i < G[u].size(); i++) { Edge& e = edges[G[u][i]]; if(d[e.to] > d[u] + e.dist) { d[e.to] = d[u] + e.dist; p[e.to] = G[u][i]; Q.push((HeapNode){d[e.to], e.to}); } } } } LL DP(int S) { if(S == 1) return 1; if(dp[S] != -1) return dp[S]; else { dp[S] = 0; int sz = G[S].size(); for(int i = 0; i < sz; i++) { Edge e = edges[G[S][i]]; if(d[e.to]
                  
                   
?
 ??
                   
?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：CodeForces 558C Amr and Chemist.. 下一篇：hdoj-1197-Specialized Four-Digi..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: