牛客网：水图（不需要返回起点来遍历所有节点的最短路径【DFS】）

链接：https://ac.nowcoder.com/acm/contest/188/C?&headNav=www
来源：牛客网
 

题目描述

小w不会离散数学，所以她van的图论游戏是送分的

小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度
小w现在在点x上
她想知道从点x出发经过每个点至少一次，最少需要走多少路

输入描述:

第一行两个整数 n,x,代表点数,和小w所处的位置
第二到第n行,每行三个整数 u,v,w,表示u和v之间有一条长为w的道路

输出描述:

一个数表示答案

示例1

输入

复制3 1 1 2 1 2 3 1

3 1
1 2 1
2 3 1

输出

复制2

2

备注:

1 ≤ n ≤ 50000 , 1 ≤ w ≤ 2147483647

思路：最差情况下，所走的路径长度一定是所有边的长度之和乘2，但是由于我们不需要每次都返回起点，因此我们可以少走些冤枉路，在这张图上，一定有一些点是属于“叶子节点”的，这里的“叶子节点”是指该节点只有一个相邻节点，并且不是起点。经分析我们发现，只有一条路径上的边可以少走一次，这是很容易想通的，因为你走到“叶子节点”的话，倘若此时还有节点没有遍历到，呢你肯定是要拐回去的，因此我们只需要找到一条最长的路径，只走一次这条路径就好了。

import javax.management.loading.MLetMBean;
import javax.swing.plaf.synth.SynthTextAreaUI;
import java.awt.*;
import java.io.CharConversionException;
import java.lang.reflect.Array;
import java.sql.SQLOutput;
import java.util.*;
import java.util.List;

public class Main {

    static class node {
        int v, w;

        public node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    private static int ans;
    private static boolean[] flag;
    private static List<List<node>> list;

    public static void main(String[] args) {

        ans = 0;
        int sum = 0;
        int n, x, u, v, w;
        Scanner in = new Scanner(System.in);

        n = in.nextInt();
        x = in.nextInt();
        flag = new boolean[n + 1];
        list = new ArrayList<>();
        for (int i = 0; i <= n; i++)
            list.add(new ArrayList<>());

        for (int i = 0; i < n - 1; i++) {
            u = in.nextInt();
            v = in.nextInt();
            w = in.nextInt();
            list.get(u).add(new node(v, w));
            list.get(v).add(new node(u, w));
            sum += w;
        }

        dfs(x, 0);

        System.out.println(sum * 2 - ans);

    }

    private static void dfs(int x, int dis) {

        flag[x] = true;
        int size = list.get(x).size();

        if (size == 1 && flag[list.get(x).get(0).v]) {
            ans = Math.max(ans, dis);
            return;
        }

        for (int i = 0; i < size; i++) {
            int nxt = list.get(x).get(i).v;
            if (flag[nxt]) continue;
            dfs(nxt, dis + list.get(x).get(i).w);
        }

    }
}

 

本文地址：https://blog.csdn.net/haut_ykc/article/details/107884143