UVA 10917 Walk Through the Forest（Dijkstra+DAG动态规划）

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

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