P8855 [POI 2002 R1] 商务旅行题目描述某地首都的商人要经常到其他城镇去做生意他们会按自己的路线去走。有NNN个城镇首都编号为111。商人从首都出发其他各城镇之间都有道路连接。任意两个城镇之间如果有直连道路在他们之间行驶需要花费单位时间。如果从首都出发能到达任意一个城镇。请你求出商人最短的旅行时间。输入格式第一行有一个整数NNN为城镇的数目。接下来N−1N-1N−1行每行两个整数aaa和bbb表示城镇aaa和城镇bbb有公路连接。接下来一个整数MMM然后MMM行每行有该商人需要顺次经过的各城镇编号。输出格式一行输出商人最短的旅行时间。输入输出样例 #1输入 #15 1 2 1 5 3 5 4 5 4 1 3 2 5输出 #17说明/提示数据范围1≤N≤300001 \le N \le 300001≤N≤30000。*保证公路网络不会存在环。C实现#includeiostream#includevectorusingnamespacestd;vectorintE[300100];intd[300100],f[300100][30];voiddfs(intu,int_f){d[u]d[_f]1;f[u][0]_f;for(inti1;i20;i){f[u][i]f[f[u][i-1]][i-1];}for(intv:E[u]){if(v_f){continue;}dfs(v,u);}}intLCA(intu,intv){if(d[u]d[v]){swap(u,v);}for(inti20;i0;i--){if(d[f[u][i]]d[v]){uf[u][i];}}if(uv){returnu;}for(inti20;i0;i--){if(f[u][i]!f[v][i]){uf[u][i];vf[v][i];}}returnf[u][0];}intmain(){intn,m,u,v,r,s0;cinn;for(inti1;in;i){cinuv;E[u].push_back(v);E[v].push_back(u);}dfs(1,0);cinm;u1;while(m--){cinv;sd[u]d[v]-2*d[LCA(u,v)];uv;}couts;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
