程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> UVA 10917 Walk Through the Forest（Dijkstra+DAG動態規劃）

UVA 10917 Walk Through the Forest（Dijkstra+DAG動態規劃）

編輯：關於C++

題意：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] 
??