题意是:在m点有两辆车,要清扫所有的路,问走的最短路。题目链接
和poj1935 差不多,poj 1935 是一个人走的最短路。
题解 所有边权和 * 2 —— 树的最长路径。
树形dp的解法不会,
#include<cstdio> #include<cstring> #include<queue> #include<iostream> using namespace std; #define FF freopen("Input.txt","r",stdin) #define mem(x,y) memset(x,y,sizeof(x)) #define ll long long #define inf 1000020 const int N=100010; int head[N]; struct Point { int v,w; int next; }edge[N*2]; int tot,dis[N]; inline void init() { mem(head,-1); tot=0; } void add(int u,int v,int w) { edge[tot].v=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } int bfs(int u,int n) { mem(dis,-1); queue<int>Q; dis[u]=0; Q.push(u); while(!Q.empty()) { int v=Q.front(); Q.pop(); for(int i=head[v];i!=-1;i=edge[i].next) { int s=edge[i].v; if(dis[s]==-1) { dis[s]=dis[v]+edge[i].w; Q.push(s); } } } int Maxn=-1; int pos=-1; for(int i=1;i<=n;i++) if(dis[i]>Maxn) { Maxn=dis[i]; pos=i; } return pos; } int main() { //FF; int n,i,m; while(~scanf("%d%d",&n,&m)) { init(); int sum=0; for(i=1;i<n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); sum+=(c*2); } int pos=bfs(m,n); pos=bfs(pos,n); printf("%d\n",sum-dis[pos]); } return 0; }