Official

D - Paid Walk Editorial by en_translator


The paths that start from vertex \(1\) and traverses an edge exactly \(L\) times can be enumerated by an algorithm like Depth-First Search (DFS).
Whether a vertex \(v\) \((1\leq v\leq N)\) satisfies the conditions in the problem statement is equivalent to whether such paths include a path whose total cost of the edges traversed is between \(S\) and \(T\) (inclusive) and the vertex after \(L\) traversals is \(v\).

Thus, starting from the state where you are at vertex \(1\) and have not traversed any edges, we can perform the following operation recursively while maintaining (the current vertex, the number of edges traversed so far, the total cost of the edges traversed so far):

  • If the number of edges traversed so far is \((L-1)\) or less, for all vertices going out from the current vertex, do the following: “Traverse the edge. When traversing, update (the current vertex, the number of edges traversed so far, the total cost of the edges traversed so far) according to the edge traversed. Then, perform this action again.”
  • If the number of edges traversed so far is \(L\), if the number of edges traversed so far is between \(S\) and \(T\), record the current vertex as a vertex that satisfies the conditions (in the problem statement).

After this procedure, the answers can be obtained by enumerating (without duplicates) the vertices recorded as applicable.

What matters here is the time complexity required for the enumeration. The important fact is that:

In a graph given in this problem, there are at most \(4^L\) paths that start from vertex \(1\) and traverse an edge exactly \(L\) times.
Here, two paths are considered different if the \(i\)-th traversed edges differ for some \(1\leq i\leq N\).

Proof We will show it by induction on $L$. If $L=1$, we have no choice but traversing an edge going out from vertex $1$, and maximum outdegree of the vertex, $4$, justifies the claim. Consider $L=k+1$ $(k\geq 1)$. A path that traverses an edge exactly $(k+1)$ times can be obtained by appending, to a path that traverses an edge exactly $k$ times, one of the edges going out from the last vertex after the $k$ traversals. Since the number of paths with exactly $k$ traversals is $4^k$ or less by assumption, and the outdegree of any vertex is $4$ or less, the number of paths with exactly $(k+1)$ traversals is at most $4^k\times 4=4^{k+1}$. This concludes the proof.

Hence, all the possible paths can be enumerated in at most \(O(L\cdot 4^L)\) time. Actually, since there are at most \(4^i\) possible states after \(i\) traversals, the complexity of the DFS above is \(O(4^L)\).
This runs fast enough under the constraints of the problem (in particular, under \(L\leq 10\)). Thus, the problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

#define N (int)200000

int l,s,t;
vector<pair<int,int> >e[N];
bool flag[N];


void dfs(int k,int d,int tot){
	if(d==l){
	  if((s<=tot)&&(tot<=t))flag[k]=true;
	  return;
	}
	if(d<l){ //just in case
		int sz=e[k].size();
		for(int i=0;i<sz;i++){
			dfs(e[k][i].first,d+1,tot+e[k][i].second);
		}
	}
	return;
}


int main() {
	int n,m;
	int u,v,c;
	cin >> n >> m >> l >> s >> t;
	for(int i=0;i<m;i++){
		cin >> u >> v >> c;
		e[u-1].push_back({v-1,c});
	}
	for(int i=0;i<n;i++)flag[i]=false;
	dfs(0,0,0);

	vector<int>ans;
	for(int i=0;i<n;i++){if(flag[i])ans.push_back(i+1);}
	int sz=ans.size();
	for(int i=0;i<sz;i++){
		cout << ans[i];
		if(i<(sz-1))cout << " ";
	}
	cout << endl;
	return 0;
}

posted:
last update: