[POJ] 2662 A Walk Through the Forest

題目網址: http://poj.org/problem?id=2662

題意: 要從辦公室走回家會經過一片森林，給定森林的點(包含辦公室-點1、家-點2)，且要求若在點A上能有邊至點B，且從B回到家比從A回到家快，就可以考慮往B走，問從點1走到點2，有幾種走法。



解法: 先求出以點2為起點至每個點的最短路徑長度(SPFA)，後以DP計算方法數，dp[i]代表從點i出發能夠走到點2的方法數，而狀態轉移方程:

dp[i] = { 1, if i == 2
  { += dp[j], if i到j有邊 && d[i] > d[j]

再以DFS從點1出發走過整個圖，最後答案即為 dp[1]。


*d[i]代表以點2為起點到點i的最短路徑長度

TAG: SPFA, DP, DFS

注意: None

程式碼:

	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <queue>
	using namespace std;
	#define N 1005
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define INF 2147483647
	typedef queue<int> QI;
	int n, m;
	int e[N][N];
	int ev[N][N];
	int el[N];
	int d[N];
	int dp[N];
	bool inQ[N];
	void spfa( void )
	{
	static int i, now, nxt;
	static QI q;
	for( i = q.size(); i; --i ) q.pop();
	for( i = 1; i <= n; ++i ) d[i] = INF;
	clr( inQ, false );
	d[2] = 0;
	q.push(2);
	inQ[2] = true;
	while( !q.empty() ) {
	now = q.front(); q.pop();
	inQ[now] = false;
	for( i = 0; i < el[now]; ++i ) {
	nxt = e[now][i];
	if( d[nxt] > d[now]+ev[now][i] ) {
	d[nxt] = d[now]+ev[now][i];
	if( !inQ[nxt] ) {
	q.push(nxt);
	inQ[nxt] = true;
	}
	}
	}
	}
	}
	const int dfs( const int now )
	{
	if( dp[now] != -1 ) return dp[now];
	int i, nxt;
	dp[now] = 0;
	for( i = 0; i < el[now]; ++i ) {
	nxt = e[now][i];
	if( d[nxt] < d[now] ) dp[now] += dfs( nxt );
	}
	return dp[now];
	}
	int main( void )
	{
	int i;
	int a, b, v;
	while( scanf( "%d", &n ) == 1 && n ) {
	scanf( "%d", &m );
	clr( e, false );
	clr( el, 0 );
	for( i = 0; i < m; ++i ) {
	scanf( "%d%d%d", &a, &b, &v );
	e[a][el[a]] = b;
	e[b][el[b]] = a;
	ev[a][el[a]++] = ev[b][el[b]++] = v;
	}
	spfa();
	clr( dp, -1 );
	dp[2] = 1;
	printf( "%d\n", dfs(1) );
	}
	return 0;
	}

view raw A Walk Through the Forest hosted with ❤ by GitHub