首页 > 代码库 > codevs 1036 商务旅行
codevs 1036 商务旅行
1036 商务旅行
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond
题目描述 Description
某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。
假设有N个城镇，首都编号为1，商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇，并且公路网络不会存在环。
你的任务是帮助该商人计算一下他的最短旅行时间。
输入描述 Input Description
输入文件中的第一行有一个整数N，1<=n<=30 000，为城镇的数目。下面N-1行，每行由两个整数a 和b (1<=a, b<=n; a<>b)组成，表示城镇a和城镇b有公路连接。在第N+1行为一个整数M，下面的M行，每行有该商人需要顺次经过的各城镇编号。
输出描述 Output Description
在输出文件中输出该商人旅行的最短时间。
样例输入 Sample Input
5
1 2
1 5
3 5
4 5
4
1
3
2
5
样例输出 Sample Output
7
思路，n个城市n-1条公路，显然是一棵树。
对于点u和点v，他们之间的最短距离(时间)，就是depth[u]+depth[v]-2*depth[lca(u,v)];
Tarjan-lca水之。
喜闻乐见的Code
#include<cstdio>#include<vector>using namespace std;#define maxn 30005int father[maxn],dad[maxn],qx[maxn],qy[maxn],ans[maxn],depth[maxn];vector<int>t[maxn],ques[maxn];inline int input() { char c=getchar();int x=0,flag=1; for(;c<‘0‘||c>‘9‘;c=getchar()) if(c==‘-‘) flag=-1; for(;c>=‘0‘&&c<=‘9‘;c=getchar()) x=(x<<1)+(x<<3)+c-‘0‘; return x*flag;}inline int find(int x) { return father[x]==x?x:father[x]=find(father[x]);}void dfs(int x) { father[x]=x; depth[x]=depth[dad[x]]+1; for(int i=0;i<t[x].size();i++) if(dad[x]!=t[x][i]) dad[t[x][i]]=x,dfs(t[x][i]); for(int i=0,y;i<ques[x].size();i++) if(dad[y=qx[ques[x][i]]^qy[ques[x][i]]^x]) ans[ques[x][i]]=find(y); father[x]=dad[x]; return;}int main() { int n=input(); for(int i=1;i<n;i++) { int u=input(),v=input(); t[u].push_back(v); t[v].push_back(u); } int m=input(),tx,ty,sum=0; tx=input(); for(int i=1;i<m;i++) { ty=input(); qx[i]=tx;qy[i]=ty; ques[qx[i]].push_back(i); ques[qy[i]].push_back(i); tx=ty; } dfs(1); for(int i=1;i<m;i++) sum+=(depth[qx[i]]+depth[qy[i]]-(depth[ans[i]]*2)); printf("%d",sum); return 0;}
codevs 1036 商务旅行
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。