UVa-10917, POJ-2662 : A Walk Through the Forest

問題概要

ノード数N(<1000)の重み付き無向グラフが与えられる。スタートからゴールまでの経路が何種類あるか求める問題。ただし、ゴールまでの距離が減少するノードにしか遷移できない。

解法

終点からの最短距離が大きい順にDPする。

acceptされたコード

計算量O(N^2*logN)。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

const int MAX_N = 1000;
const int INF = 1<<29;

int N;
int graph[MAX_N][MAX_N];
int dist[MAX_N], dp[MAX_N], order[MAX_N];

void init(){
	int M;
	scanf("%d", &M);

	memset(graph, -1, sizeof(graph));
	while(M--){
		int x, y, z;
		scanf("%d%d%d",&x,&y,&z);
		x--; y--;
		graph[x][y] = graph[y][x] = z;
	}
}

struct state{
	int cur, dist;
};

bool operator<(const state& lhs, const state& rhs){
	return lhs.dist > rhs.dist;
}

int solve(){

	//dijkstra
	fill(dist, dist+N, INF);
	priority_queue<state> que;
	que.push( (state){1, 0} );
	dist[1] = 0;

	while(!que.empty()){
		state tp = que.top(); que.pop();
		int cur = tp.cur, d = tp.dist;
		if(dist[cur] < d){
			continue;
		}

		for(int i=0; i<N; i++)if(graph[cur][i] != -1){
			int nd = d + graph[cur][i];
			if(nd < dist[i]){
				dist[i] = nd;
				que.push( (state){i, nd} );
			}
		}
	}

	for(int i=0; i<N; i++){
		order[i] = i;
	}

	//距離が遠い順にソート
	for(int i=0; i<N; i++){
		for(int j=0; j+1<N; j++)if(dist[order[j+1]] > dist[order[j]]){
			swap(order[j+1], order[j]);
		}
	}

	memset(dp, 0, sizeof(dp));
	dp[0] = 1;

	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++)if(graph[order[i]][order[j]] != -1 && dist[order[j]] < dist[order[i]]){
			dp[order[j]] += dp[order[i]];
		}
	}

	return dp[1];
}

int main(){
	while(scanf("%d", &N), N){
		init();
		printf("%d\n", solve());
	}
	return 0;
}