题目链接：http://poj.org/problem?id=1849

       题意是有n个点，n-1条边(树形图)，在s点放两个机器人，问这两个机器人遍历完所有的点的最少花费(不用回到原点)。

       这道题的结论就是边权和*2减去树的直径，其实不难理解，让两个机器人沿着直径走，去扫经过的分支都有一个来回，而最长的直径是只走一遍的，然而不管从那个点开始都按这个思路去走的结果是最优的，画画图想一下就好了。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
  int to,next,w;
}Edge[maxn];
int head[maxn],num;
int dist[maxn];
bool vis[maxn];
int n,s;

void init(){
  for(int i=0;i<=n;i++){
    head[i] = -1;
  }
  num = 0;
}

void add(int u,int v,int w){
  Edge[num].to = v;
  Edge[num].w = w;
  Edge[num].next = head[u];
  head[u] = num ++;
}

void bfs(int x){
  queue<int> q;
  memset(dist,0,sizeof(dist));
  memset(vis,false,sizeof(vis));
  q.push(x);
  while(!q.empty()){
    int u = q.front();
    q.pop();
    vis[to] = true;
    for(int i=head[u];i!=-1;i=Edge[i].next){
      int to = Edge[i].to;
      if(vis[to] == false){
        vis[to] = true;
        dist[to] = dist[u] + Edge[i].w;
        q.push(to);
      }
    }
  }
}

int main()
{
  int sum = 0;
  scanf("%d%d",&n,&s);
  init();
  for(int i=0;i<n-1;i++){
    int u, v, w;
    scanf("%d%d%d",&u,&v,&w);
    sum += w;
    add(u, v, w);
    add(v, u, w);
  }
  bfs(1);
  int pos = 0;
  int Max = 0;
  for(int i=1;i<=n;i++){
    if(Max < dist[i]){
      Max = dist[i];
      pos = i;
    }
  }
  bfs(pos);
  int ans = 0;
  for(int i=1;i<=n;i++) ans = max(ans, dist[i]);
  printf("%d\n",sum * 2 - ans);
  return 0;
}