首页 > 代码库 > UVa 10917 林中漫步

UVa 10917 林中漫步

2024-09-12 09:52:08   215人阅读

https://vjudge.net/problem/UVA-10917

题意：

给出一个图，求出从1走到2共有多少种走法。前提是他只沿着满足如下条件的道路（A，B）走：存在一条从B出发回家的路径，比所有从A出发回家的路径都短。

 

思路：

首先用Dijkstra算法求出每个点到家的最短路径，那么题目的要求也就变成了d[B]<d[A],这样，我们创建了一个新的图，当且仅当d[B]<d[A]时加入有向边A->B,这样就是一个DAG，直接用动态规划计数。

  1 #include <iostream>    2 #include <cstring>    3 #include <algorithm>     4 #include <vector>  5 #include <queue>  6 using namespace std;  7   8 const int maxn = 1000 + 5;  9 const int INF = 0x3f3f3f3f; 10  11 int n, m; 12  13 struct Edge 14 { 15     int from, to, dist; 16     Edge(int u, int v, int d) :from(u), to(v), dist(d){} 17 }; 18  19 struct HeapNode 20 { 21     int d, u; 22     HeapNode(int x, int y) :d(x), u(y){} 23     bool operator < (const HeapNode& rhs) const 24     { 25         return d>rhs.d; 26     } 27 }; 28  29 struct Dijkstra 30 { 31     int n, m; 32     vector<Edge> edges; 33     vector<int> G[maxn]; 34     bool done[maxn]; 35     int d[maxn]; 36     int p[maxn]; 37     int dp[maxn]; 38  39     void init(int n) 40     { 41         this->n = n; 42         for (int i = 0; i < n; i++) 43             G[i].clear(); 44         edges.clear(); 45     } 46  47     void AddEdge(int from, int to, int dist) 48     { 49         edges.push_back(Edge(from, to, dist)); 50         int m = edges.size(); 51         G[from].push_back(m - 1); 52     } 53  54     void dijkstra(int s) 55     { 56         priority_queue<HeapNode> Q; 57         for (int i = 0; i < n; i++)  d[i] = INF; 58         memset(done, 0, sizeof(done)); 59         d[s] = 0; 60         Q.push(HeapNode(0, s)); 61         while (!Q.empty()) 62         { 63             HeapNode x = Q.top(); 64             Q.pop(); 65             int u = x.u; 66             if (done[u])  continue; 67             done[u] = true; 68             for (int i = 0; i < G[u].size(); i++) 69             { 70                 Edge& e = edges[G[u][i]]; 71                 if (d[e.to]>d[u] + e.dist) 72                 { 73                     d[e.to] = d[u] + e.dist; 74                     p[e.to] = e.from; 75                     Q.push(HeapNode(d[e.to], e.to)); 76                 } 77             } 78         } 79     } 80  81     int DP(int s) 82     { 83         if (s == 1)  return 1; 84         if (dp[s] != -1)  return dp[s]; 85         dp[s] = 0; 86         for (int i = 0; i < G[s].size(); i++) 87         { 88             Edge e = edges[G[s][i]]; 89             if (d[e.to] < d[s])  dp[s] += DP(e.to); 90         } 91         return dp[s]; 92     } 93 }t; 94  95 int main() 96 { 97     //freopen("D:\\input.txt", "r", stdin); 98     int u, v, d; 99     while (~scanf("%d", &n) && n)100     {101         scanf("%d", &m);102         t.init(n);103         for (int i = 0; i < m; i++)104         {105             scanf("%d%d%d", &u, &v, &d);106             t.AddEdge(u - 1, v - 1, d);107             t.AddEdge(v - 1, u - 1, d);108         }109         t.dijkstra(1);110         memset(t.dp, -1, sizeof(t.dp));111         t.DP(0);112         printf("%d\n", t.dp[0]);113     }114     return 0;115 }

 

UVa 10917 林中漫步


联系
我们