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; }