Hlg 1750 【树的最长路径】.cpp

题意：

　　小A要从第一个城市出发走遍所有城市..

　　但是想要尽量走少一点路..

　　给出两个城市之间连接的距离..问最少需要走多少距离..

思路：

　　如果要回到原点..最短距离相当于每一段路都走两遍..

　　现在并不需要走回第一个城市..只要走遍所有城市就好..

　　所以找到一条从第一个城市开始的最长的路..然后用总长度*2-最长的路..

　　得到的就是最短的路了..

　　求最短路可以用dfs..bfs..

Tips：

　　深搜的时候要记得用一个vis数组..

　　否则会死循环..因为是一个无向图..

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int MAXM = 10000010;
 7 const int MAXN = 100010;
 8 
 9 struct Node
10 {
11     int to;
12     int next;
13     int w;
14 }edge[MAXM];
15 int tot;
16 int head[MAXN];
17 
18 void add(int s, int u, int w)
19 {
20     edge[tot].to = u;
21     edge[tot].next = head[s];
22     edge[tot].w = w;
23     head[s] = tot++;
24 
25     edge[tot].to = s;
26     edge[tot].next = head[u];
27     edge[tot].w = w;
28     head[u] = tot++;
29 }
30 
31 int ans;
32 bool vis[MAXN];
33 
34 void dfs(int s, int cnt) {
35     ans = max(ans, cnt);
36 //printf("1_____s:%d cnt:%d\n", s, cnt);
37     for (int i = head[s]; i; i = edge[i].next) {
38         int to = edge[i].to;
39         if (!vis[to]) {
40             vis[to] = true;
41             dfs(edge[i].to, cnt+edge[i].w);
42             vis[to] = false;
43         }
44 
45     }
46 }
47 
48 int main()
49 {
50     int n, sum;
51     int a, b, c;
52     while(~scanf("%d", &n)) {
53         ans = sum = 0;
54         tot = 1;
55         memset(vis, false, sizeof(vis));
56         memset(head, 0, sizeof(head));
57         for (int i = 0; i < n-1; ++i) {
58             scanf("%d %d %d", &a, &b, &c);
59             add(a, b, c);
60             sum += c;
61         }
62         vis[1] = true;
63         dfs(1, 0);
64         printf("%d\n", sum*2-ans);
65     }
66     return 0;
67 }

链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1750