首页 > 代码库 > UVa 10917 林中漫步
UVa 10917 林中漫步
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 林中漫步
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。