# 醋溜便当## 题目背景伊吹萃香是幻想乡的跟踪狂。## 题目描述萃香每天会派自己的分身巡视整个幻想乡。幻想乡可以被视为一张 $n$ 个点 $m$ 条边的无向图边有长度。萃香希望巡视到幻想乡的每个节点于是她在每个节点 $i$ 都安排了一个分身分身会沿着一条路径从 $i$ 出发再回到 $i$。可以多次经过同一条边也可以多次经过同一个点包括 $bm i$。如果分身巡视的路径太短会被居民怀疑有跟踪的风险

首先，我们可以使用深度优先搜索（DFS）来判断从每个节点出发是否存在符合条件的回路。

具体而言，对于每个节点 $i$，我们可以从节点 $i$ 出发，进行一次深度优先搜索，寻找一条路径使得路径的长度在 $[x, k \times x]$ 之间。在搜索过程中，我们需要记录当前路径的长度，并且在路径长度超过 $k \times x$ 后立即返回。

为了避免重复访问同一个节点，我们可以使用一个布尔数组 $visited$ 来记录每个节点是否已经被访问过。在进行深度优先搜索时，我们可以将当前节点标记为已访问，并继续搜索与当前节点相邻且未被访问过的节点。

如果搜索过程中找到了一条满足条件的路径，我们可以立即返回结果，将节点 $i$ 标记为可以找到符合条件的回路。否则，我们将节点 $i$ 标记为无法找到符合条件的回路。

最后，我们遍历所有节点，根据它们的标记输出结果。

时间复杂度分析：对于每个节点，我们最多访问它的所有相邻节点一次，因此总的时间复杂度为 $O(n + m)$。

空间复杂度分析：我们需要使用一个大小为 $n$ 的布尔数组 $visited$ 来记录节点的访问情况，因此空间复杂度为 $O(n)$。

下面给出使用深度优先搜索实现的示例代码：

def dfs(node, length, x, k, visited, graph):
    visited[node] = True

    if length > k * x:
        return

    if length >= x:
        return True

    for neighbor, weight in graph[node]:
        if not visited[neighbor]:
            if dfs(neighbor, length + weight, x, k, visited, graph):
                return True

    visited[node] = False
    return False


def vinegar_lunch(n, m, x, k, edges):
    graph = [[] for _ in range(n + 1)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))

    result = [0] * (n + 1)
    visited = [False] * (n + 1)

    for i in range(1, n + 1):
        if dfs(i, 0, x, k, visited, graph):
            result[i] = 1

    return result


n, m, x, k = map(int, input().split())
edges = []
for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((u, v, w))

result = vinegar_lunch(n, m, x, k, edges)
print(' '.join(map(str, result)))

时间复杂度：$O(n+m)$

空间复杂度：$O(n)