题意:一个国家中的城市以树形结构连接,选定一定要旅游的城市,在首都出发, 问环游的最短路径(可以不停止在起点)。
做法:建立两个状态,从i点出发回到i点和不回,这样就可以了
#include<cstdio> #include<cstring> const int LMT=50002; int sum[2][LMT],next[LMT],all,is[LMT]; struct line { int u,v,next,len; }e[LMT<<1]; void init(void) { memset(is,0,sizeof(is)); memset(sum,0,sizeof(sum)); memset(next,-1,sizeof(next)); all=0; } void insert(int u,int v,int len) { e[all].u=u; e[all].v=v; e[all].len=len; e[all].next=next[u]; next[u]=all++; } void dfs(int u,int pre) { int v,x,len,tem; for(x=next[u];x!=-1;x=e[x].next) if(e[x].v!=pre) { v=e[x].v;len=e[x].len; dfs(v,u); if(is[v]) { tem=len+sum[0][u]+sum[1][v]; if(sum[1][u]+sum[0][v]+(len<<1)>tem) sum[1][u]=tem; else sum[1][u]=sum[1][u]+sum[0][v]+(len<<1); sum[0][u]+=(len<<1)+sum[0][v]; is[u]=1; } } } int main(void) { int k,n,i,u,v,len,m; while(~scanf("%d%d",&n,&k)) { init(); for(i=1;i<n;++i) { scanf("%d%d%d",&u,&v,&len); insert(u,v,len); insert(v,u,len); } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d",&u); is[u]=1; } dfs(k,-1); printf("%d\n",sum[1][k]); } return 0; }