Codechef-CIELTOMY : Ciel and Tomya

問題概要

無向重み付きグラフが与えられるのである点からある点までの最短路のパスの総数を求める問題。

解法

サイズが小さいのと重みが非負なのでDijkstraするまでもなく(位置、距離)を組にしたDPでやるのが簡単。

acceptされたコード

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

typedef long long int64;

const int MAX_N = 10;
const int MAX_C = 10;

int64 nums[MAX_N][MAX_N*MAX_C + 1];

struct Edge {
	int from, to, cost;
	Edge() {}
	Edge(int from, int to, int cost):from(from), to(to), cost(cost){}
};

int N, M;
vector<Edge> graph[MAX_N];

void init() {
	for (int i = 0; i < MAX_N; ++i) {
		graph[i].clear();
	}
	memset(nums, 0, sizeof(nums));
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int from, to, cost;
		scanf("%d%d%d", &from, &to, &cost);
		--from;
		--to;
		graph[from].push_back(Edge(from, to, cost));
		graph[to  ].push_back(Edge(to, from, cost));
	}
}

int64 solve() {
	nums[0][0] = 1;
	for (int dist = 0; dist <= N*MAX_C; ++dist) {
		for (int v = 0; v < N; ++v) {
			for (int i = 0; i < (int)graph[v].size(); ++i) {
				int tar = graph[v][i].to;
				int ncost = dist + graph[v][i].cost;
				if (ncost <= N * MAX_C) {
					nums[tar][ncost] += nums[v][dist];
				}
			}
		}
	}

	for (int i = 0; i <= N*MAX_C; ++i) {
		if (nums[N-1][i]) {
			return nums[N-1][i];
		}
	}
	return 1;
}

int main() {
	int T;
	scanf("%d", &T);
	for (int _ = 0; _ < T; ++_) {
		init();
		printf("%lld\n", solve());
	}
	return 0;
}