Atcoder解いてみた AtCoder Beginner Contest D - Paid Walk

AtCoder Beginner Contest D - Paid Walk

問題はこちら

回答

グラフが複雑で、最短経路を求めればいいわけでもなく、一度解説見てヒントを得た
全探索系で解こうとしていることだけ確認した
改めてパラメータの取りうる範囲を確認し、Lが異常に小さいのと、出次数の最大値が4であることに着目
し、4^Lの全探索を行うこととした

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

struct Edge {
	int v;
	long long c;
};

int N;
int M;

// 移動回数制約L
int L;

// コスト制約 S以上T以下
long long S;
long long T;

std::vector<std::vector<Edge>> Mat;
std::set<int> ans;

long long total = 0;
// c:sに行くにあたってのコスト
void solve(long long& l, const int& s, const long long& c) {
	l++;
	total += c;

	// lの判定
	if (l == L) {

		// コスト制約満たす
		if (S <= total && total <= T) {
			ans.insert(s+1);
		}

		// これ以上移動しないため、戻る
		l--; // 移動できず戻る場合は回数を1戻す
		total -= c;  // 移動できず戻る場合はコストを戻す
		//std::cout << "return l=L"<<std::endl;
		return;
	}

	int numEdge = Mat[s].size();
	
	// 移動できない場合
	if (numEdge == 0) {
		l--; // 移動できず戻る場合は回数を1戻す
		total -= c;  // 移動できず戻る場合はコストを戻す
		//std::cout << "return no edge" << std::endl;
		return;
	}

	// 辺の探索
	for (int i = 0; i < numEdge; i++) {

		Edge tEdge = Mat[s][i];

		// 隣接点を起点に探索
		solve(l, tEdge.v, tEdge.c);
	}

	// 隣接点を全て探索し、これ以上移動できない
	l--; // 移動できず戻る場合は回数を1戻す
	total -= c;  // 移動できず戻る場合はコストを戻す
}

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N >> M >> L >> S >> T;

	Mat.resize(N);
	for (int i = 0; i < M; i++) {
		Edge edge;
		int u;
		std::cin >> u >> edge.v >> edge.c;
		u--;
		edge.v--;

		Mat[u].push_back(edge);
	}

	long long l = -1; // 初期値
	int s = 0;
	solve(l, s, 0LL);

	for (auto itr = ans.begin(); itr != ans.end(); itr++) {
		std::cout << *itr << " ";
	}

	return 0;
}

ただ、上記のコードは、l と total を外側で共有しているため、「どのreturn経路でも必ず戻す」 を保証するのが難しくなっており、バグが発生しやすいコードになっている
以下のように、値渡しをして、状態を共有しなければ、状態管理が単純になり、バグも起き辛くなる
今後は、特に再帰処理では、累積値や深さをグローバル・参照で管理すると復元漏れが起きやすいため、可能なら値渡しで状態を持たせる。

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

struct Edge {
	int v;
	long long c;
};

int N;
int M;

// 移動回数制約L
int L;

// コスト制約 S以上T以下
long long S;
long long T;

std::vector<std::vector<Edge>> Mat;
std::set<int> ans;

// c:sに行くにあたってのコスト
void solve(long long l, long long total, const int& s, const long long& c) {
	l++;
	total += c;

	// lの判定
	if (l == L) {
		// コスト制約満たす
		if (S <= total && total <= T) {
			ans.insert(s + 1);
		}
		return;
	}

	int numEdge = Mat[s].size();

	// 移動できない場合
	if (numEdge == 0) {
		return;
	}

	// 辺の探索
	for (int i = 0; i < numEdge; i++) {

		Edge tEdge = Mat[s][i];

		// 隣接点を起点に探索
		solve(l, total, tEdge.v, tEdge.c);
	}
}


int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N >> M >> L >> S >> T;

	Mat.resize(N);
	for (int i = 0; i < M; i++) {
		Edge edge;
		int u;
		std::cin >> u >> edge.v >> edge.c;
		u--;
		edge.v--;

		Mat[u].push_back(edge);
	}

	long long l = -1; // 初期値
	int s = 0;
	long long total = 0;

	solve(l, total, s, 0LL);

	for (auto itr = ans.begin(); itr != ans.end(); itr++) {
		std::cout << *itr << " ";
	}

	return 0;
}