A Walk Through the Forest
题目分析:
写了一个c++版的,居然在杭电上CE了。在北大上就神奇的过了。
回归本题题意。题目意思是,给你一些点和一些边,而你选的边需要满足如下这个条件。(A,B):存在一条从B出发回家的路径,比所有从A出发回家的路径都短。你的任务是计算一共有几条不同的回家路径。注意本题不是叫你求最短路径,而是在解题过程中要运用到最短路径而已。
算法分析:
Dijkstra+记忆化搜索。
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdio> #include <cstring> using namespace std; const int INF = 1e7; const int maxn = 1e3 + 5; struct HeapNode{ //堆 int d,u; bool operator<(const HeapNode &rhs)const{ return d > rhs.d; } }; struct Edge{ //边集 int from,to,dist; }; vector<Edge> edges; vector<int> G[maxn]; //每个节点出发的编号 int d[maxn],dp[maxn]; void Clear() { for(int i = 0;i < maxn;++i) G[i].clear(),d[i] = INF,dp[i] = -1; } void AddEdge(int from,int to,int d) { Edge e; e.from = from; e.to = to; e.dist = d; edges.push_back(e); int m = edges.size(); G[from].push_back(m-1); } void Dijkstra(int s) { bool done[maxn]; HeapNode tmp; priority_queue<HeapNode> Q; memset(done,0,sizeof(done)); d[s] = 0; tmp.d = d[s]; tmp.u = s; Q.push(tmp); 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 < (int)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[i][i]; tmp.d = d[e.to]; tmp.u = e.to; Q.push(tmp); } } } } int DP(int s) { if(dp[s]!=-1) return dp[s]; if(s == 2) return 1; int sum = 0; for(int i = 0;i < (int)G[s].size();++i){ Edge& e = edges[G[s][i]]; if(d[s] > d[e.to]){ if(dp[e.to] != -1) sum += dp[e.to]; else sum += DP(e.to); } } //sum += dp[s]; dp[s] = sum; return dp[s]; } int main() { // freopen("Input.txt","r",stdin); int n,m; while(scanf("%d",&n),n) { int x,y,w; Clear(); scanf("%d",&m); for(int i = 0;i < m;++i){ scanf("%d%d%d",&x,&y,&w); AddEdge(x,y,w); AddEdge(y,x,w); } Dijkstra(2); printf("%d\n", DP(1)); } return 0; }
在北大上才能过。
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdio> #include <cstring> using namespace std; const int INF = 1e7; const int maxn = 1e3 + 5; struct HeapNode{ int d,u; bool operator<(const HeapNode &rhs)const{ return d > rhs.d; } }; struct Edge{ int from,to,dist; }; vector<Edge> edges; vector<int> G[maxn]; int d[maxn],dp[maxn]; void Clear() { for(int i = 0;i < maxn;++i) G[i].clear(),d[i] = INF,dp[i] = -1; } void AddEdge(int from,int to,int d) { edges.push_back((Edge){from,to,d}); int m = edges.size(); G[from].push_back(m-1); } void Dijkstra(int s) { bool done[maxn]; priority_queue<HeapNode> Q; memset(done,0,sizeof(done)); d[s] = 0; Q.push((HeapNode){d[s],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 < (int)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[i][i]; Q.push((HeapNode){d[e.to],e.to}); } } } } int DP(int s) { if(dp[s]!=-1) return dp[s]; if(s == 2) return 1; int sum = 0; for(int i = 0;i < (int)G[s].size();++i){ Edge& e = edges[G[s][i]]; if(d[s] > d[e.to]){ if(dp[e.to] != -1) sum += dp[e.to]; else sum += DP(e.to); } } //sum += dp[s]; dp[s] = sum; return dp[s]; } int main() { // freopen("Input.txt","r",stdin); int n,m; while(scanf("%d",&n),n) { int x,y,w; Clear(); scanf("%d",&m); for(int i = 0;i < m;++i){ scanf("%d%d%d",&x,&y,&w); AddEdge(x,y,w); AddEdge(y,x,w); } Dijkstra(2); //for(int i = 1;i <= n;++i)printf("id = %d d = %d\n",i,d[i]); printf("%d\n", DP(1)); } return 0; }
POJ&&HDU A Walk Through the Forest,布布扣,bubuko.com
POJ&&HDU A Walk Through the Forest
原文:http://blog.csdn.net/zhongshijunacm/article/details/20711713