树的直径(题目）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<queue>
 4 #include<vector>
 5 using namespace std;
 6 const int maxn = 24000;
 7 int vis[maxn];//把走过的点进行标记
 8 int dis[maxn];//到达每个点所需要走的路径长度。
 9 
10 vector<pair<int, int> >A[maxn];
11 long long ans = 0;;
12 int point = 0;
13 void bfs(int x)
14 {
15     memset(vis, 0, sizeof(vis));
16     memset(dis, 0, sizeof(dis));
17     queue<int> que;
18     que.push(x);
19     vis[x] = 1;
20     while (!que.empty()){
21         int f = que.front();
22         que.pop();
23         if (dis[f] > ans){
24             ans = dis[f];
25             point = f;
26         }
27         pair<int, int> p;
28         for (int i = 0; i < A[f].size(); i++){ //开始搜索以f为起点的所有的pair
29             p = A[f][i];                 //这一行是不是更能证明A[x][y]这个二维数组指向的就是一个pair;
30             if (vis[p.first] == 0){          //如果这个点没有走过则接着走。
31                 vis[p.first] = 1;           //标记这个点。
32                 dis[p.first] = dis[f] + p.second;//p.first代表一条边的中点，p.second代表这条边的权值。
33                 que.push(p.first);
34             }
35         }
36 
37     }
38 }
39 int main()
40 {
41     int m, n;
42     int a, b, c;
43     int sum = 0;
44     cin >> m >> n;
45     for (int i = 0; i < m - 1; i++) {
46         cin >> a >> b >> c;
47         A[a].push_back(make_pair(b, c));
48         A[b].push_back(make_pair(a, c));//建图
49         sum += c;
50     }
51     memset(dis, 0, sizeof(dis));
52     memset(vis, false, sizeof(vis));
53     bfs(1);
54     ans = 0;
55     bfs(point);//两次bfs求树的直径
56     cout << 2 * sum - ans << endl;
57     return 0;
58 }