P1294 高手去散步

calendar May 11, 2026 · 6 分钟阅读 · 深度优先搜索 图论 枚举  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1294
难度 普及-
知识点 深度优先搜索、图论、枚举

题目描述

高手们想要去散步！给定 n 个景点和 m 条道路，每条道路连接两个景点且有固定长度。

从任意一个景点出发，散步时不能重复经过同一个景点（即每个景点最多经过一次），问最远能走多长的距离？

输入格式

  • 第一行：两个整数 n 和 m（景点数和道路数）
  • 接下来 m 行：每行三个整数 u、v、w，表示景点 u 和景点 v 之间有一条长度为 w 的道路

输出格式

  • 输出一个整数，表示最长的散步距离

样例

输入 #1：

4 5
1 2 1
2 3 1
3 4 1
4 1 2
1 3 2

输出 #1：

5

解题思路

核心思想

这是一道经典的 DFS 枚举路径 问题。

关键约束：每个景点最多经过一次 → 这意味着路径是一条简单的路径（Simple Path），不能走回头路。

暴力枚举：由于 n ≤ 30，从每个景点出发，DFS 遍历所有可能的路径，统计最大值。

算法流程

1. 构建无向图（邻接矩阵存储）
2. 对每个景点 i：
   - 标记 i 已访问
   - 从 i 开始 DFS
   - 更新全局最大值
3. 输出最大值

剪枝策略

  • 已访问标记：g[i] = true/false 防止重复经过
  • 搜索终止：当前景点没有未访问的相邻点时，DFS 结束

完整代码

C++

#include <bits/stdc++.h>

namespace {

// 最大景点数量
constexpr int kMaxN = 30;
// 邻接矩阵存储无向图
int graph[kMaxN + 1][kMaxN + 1];
// 景点是否已访问
bool visited[kMaxN + 1];
// 最大散步距离
int maxDistance;

// 四个方向的偏移量（下、右、上、左）
int dir_x[5] = {0, 1, -1, 0, 0};
int dir_y[5] = {0, 0, 0, 1, -1};

/**
 * DFS 枚举所有不重复经过的路径
 * @param current 当前所在景点编号
 * @param distance 已走过的总距离
 */
void DfsSearch(int current, int distance) {
    // 更新最大距离
    maxDistance = std::max(maxDistance, distance);

    // 尝试走到相邻且未访问的景点
    for (int next = 1; next <= kMaxN; ++next) {
        if (!visited[next] && graph[current][next] > 0) {
            visited[next] = true;
            DfsSearch(next, distance + graph[current][next]);
            visited[next] = false;
        }
    }
}

}  // namespace

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

    int n, m;
    std::cin >> n >> m;

    // 初始化邻接矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            graph[i][j] = 0;
        }
    }

    // 读入道路信息（无向图）
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        std::cin >> u >> v >> w;
        graph[u][v] = w;
        graph[v][u] = w;
    }

    // 从每个景点出发尝试 DFS
    for (int start = 1; start <= n; ++start) {
        std::memset(visited, 0, sizeof(visited));
        visited[start] = true;
        DfsSearch(start, 0);
    }

    std::cout << maxDistance << "\n";
    return 0;
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

const maxN = 30

var graph [maxN + 1][maxN + 1]int
var visited [maxN + 1]bool
var maxDistance int
var totalNodes int

func dfsSearch(current, distance int) {
	if distance > maxDistance {
		maxDistance = distance
	}

	for next := 1; next <= totalNodes; next++ {
		if !visited[next] && graph[current][next] > 0 {
			visited[next] = true
			dfsSearch(next, distance+graph[current][next])
			visited[next] = false
		}
	}
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var m int
	fmt.Fscan(in, &totalNodes, &m)

	for i := 1; i <= m; i++ {
		var u, v, w int
		fmt.Fscan(in, &u, &v, &w)
		graph[u][v] = w
		graph[v][u] = w
	}

	for start := 1; start <= totalNodes; start++ {
		for i := 1; i <= totalNodes; i++ {
			visited[i] = false
		}
		visited[start] = true
		dfsSearch(start, 0)
	}

	fmt.Println(maxDistance)
}

Java

import java.io.*;
import java.util.*;

public class Main {
    private static final int MAX_N = 30;
    private static int[][] graph = new int[MAX_N + 1][MAX_N + 1];
    private static boolean[] visited = new boolean[MAX_N + 1];
    private static int maxDistance;
    private static int totalNodes;

    /**
     * DFS 枚举所有不重复经过的路径
     */
    private static void dfsSearch(int current, int distance) {
        maxDistance = Math.max(maxDistance, distance);

        for (int next = 1; next <= totalNodes; next++) {
            if (!visited[next] && graph[current][next] > 0) {
                visited[next] = true;
                dfsSearch(next, distance + graph[current][next]);
                visited[next] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        totalNodes = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph[u][v] = w;
            graph[v][u] = w;
        }

        for (int start = 1; start <= totalNodes; start++) {
            for (int i = 1; i <= totalNodes; i++) {
                visited[i] = false;
            }
            visited[start] = true;
            dfsSearch(start, 0);
        }

        System.out.println(maxDistance);
    }
}

Python

import sys
sys.setrecursionlimit(10000)

MAX_N = 30

graph = [[0] * (MAX_N + 1) for _ in range(MAX_N + 1)]
visited = [False] * (MAX_N + 1)
max_distance = 0
total_nodes = 0


def dfs_search(current: int, distance: int) -> None:
    """DFS 枚举所有不重复经过的路径"""
    global max_distance
    max_distance = max(max_distance, distance)

    for next_node in range(1, total_nodes + 1):
        if not visited[next_node] and graph[current][next_node] > 0:
            visited[next_node] = True
            dfs_search(next_node, distance + graph[current][next_node])
            visited[next_node] = False


def main() -> None:
    global total_nodes, max_distance

    data = sys.stdin.read().split()
    it = iter(data)
    total_nodes = int(next(it))
    m = int(next(it))

    for _ in range(m):
        u = int(next(it))
        v = int(next(it))
        w = int(next(it))
        graph[u][v] = w
        graph[v][u] = w

    for start in range(1, total_nodes + 1):
        for i in range(1, total_nodes + 1):
            visited[i] = False
        visited[start] = True
        dfs_search(start, 0)

    print(max_distance)


if __name__ == "__main__":
    main()

JavaScript

'use strict';

const MAX_N = 30;

let graph;
let visited;
let maxDistance;
let totalNodes;

function dfsSearch(current, distance) {
    maxDistance = Math.max(maxDistance, distance);

    for (let next = 1; next <= totalNodes; next++) {
        if (!visited[next] && graph[current][next] > 0) {
            visited[next] = true;
            dfsSearch(next, distance + graph[current][next]);
            visited[next] = false;
        }
    }
}

function main() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split(/\s+/);
    totalNodes = parseInt(input[0], 10);
    const m = parseInt(input[1], 10);

    graph = Array.from({ length: MAX_N + 1 }, () => new Array(MAX_N + 1).fill(0));
    visited = new Array(MAX_N + 1).fill(false);
    maxDistance = 0;

    let idx = 2;
    for (let i = 0; i < m; i++) {
        const u = parseInt(input[idx++], 10);
        const v = parseInt(input[idx++], 10);
        const w = parseInt(input[idx++], 10);
        graph[u][v] = w;
        graph[v][u] = w;
    }

    for (let start = 1; start <= totalNodes; start++) {
        for (let i = 1; i <= totalNodes; i++) {
            visited[i] = false;
        }
        visited[start] = true;
        dfsSearch(start, 0);
    }

    console.log(maxDistance);
}

main();

关键代码讲解

1. 图的存储

graph[u][v] = w;  // 存储道路长度
graph[v][u] = w;  // 无向图，双向存储

使用邻接矩阵存储无向带权图，方便 O(1) 查找两点间距离。

2. 访问标记

bool visited[kMaxN + 1];

防止重复经过同一个景点，这是 DFS 枚举路径的核心。

3. DFS 递归搜索

void DfsSearch(int current, int distance) {
    maxDistance = std::max(maxDistance, distance);
    
    for (int next = 1; next <= kMaxN; ++next) {
        if (!visited[next] && graph[current][next] > 0) {
            visited[next] = true;
            DfsSearch(next, distance + graph[current][next]);
            visited[next] = false;  // 回溯
        }
    }
}

回溯是关键：走完一条路径后，要 visited[next] = false 释放标记，才能从其他路径再次访问该节点。

4. 多起点枚举

for (int start = 1; start <= n; ++start) {
    std::memset(visited, 0, sizeof(visited));
    visited[start] = true;
    DfsSearch(start, 0);
}

题目要求从任意景点出发，所以要从每个景点都尝试一次 DFS。

复杂度分析

方法 时间复杂度 空间复杂度
DFS 枚举 O(n!) 最坏情况 O(n)

说明：

  • 时间复杂度是指数级，但 n ≤ 30 实际可解（每个点最多有 n-1 条边）
  • 空间复杂度 O(n) 用于递归栈和访问标记数组

易错点

  1. 无向图双向存储：graph[u][v] 和 graph[v][u] 都要赋值
  2. 回溯恢复状态：visited[next] = false 不能遗漏
  3. 多起点枚举：不要只从景点 1 开始，要遍历所有起点
  4. 0 距离更新：DFS 开始前就要更新 maxDistance，因为可能只停在起点

类似题目