1036 商務(wù)旅行

?

?時(shí)間限制: 1 s ?空間限制: 128000 KB ?題目等級(jí) : 鉆石 Diamond 題解 ?查看運(yùn)行結(jié)果 題目描述?Description

某首都城市的商人要經(jīng)常到各城鎮(zhèn)去做生意，他們按自己的路線去做，目的是為了更好的節(jié)約時(shí)間。

假設(shè)有N個(gè)城鎮(zhèn)，首都編號(hào)為1，商人從首都出發(fā)，其他各城鎮(zhèn)之間都有道路連接，任意兩個(gè)城鎮(zhèn)之間如果有直連道路，在他們之間行駛需要花費(fèi)單位時(shí)間。該國(guó)公路網(wǎng)絡(luò)發(fā)達(dá)，從首都出發(fā)能到達(dá)任意一個(gè)城鎮(zhèn)，并且公路網(wǎng)絡(luò)不會(huì)存在環(huán)。

你的任務(wù)是幫助該商人計(jì)算一下他的最短旅行時(shí)間。

輸入描述?Input Description

輸入文件中的第一行有一個(gè)整數(shù)N，1<=n<=30 000，為城鎮(zhèn)的數(shù)目。下面N-1行，每行由兩個(gè)整數(shù)a?和b?(1<=a,?b<=n; a<>b)組成，表示城鎮(zhèn)a和城鎮(zhèn)b有公路連接。在第N+1行為一個(gè)整數(shù)M，下面的M行，每行有該商人需要順次經(jīng)過的各城鎮(zhèn)編號(hào)。

輸出描述?Output Description

?? ?在輸出文件中輸出該商人旅行的最短時(shí)間。

樣例輸入?Sample Input 5 1 2 1 5 3 5 4 5 4 1 3 2 5 樣例輸出?Sample Output

7

?

?

lca裸題

最短距離為每?jī)蓚€(gè)相鄰的點(diǎn)到lca的距離。

#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 300000 using namespace std; bool vis[N]; int n,m,x,y,tot,lca,ans; int a[N],fa[N],deep[N],size[N],top[N],head[N]; int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}return x*f; } struct Edge {int from,to,next; }edge[N]; int add(int x,int y) {tot++;edge[tot].to=y;edge[tot].next=head[x];head[x]=tot; } int dfs(int x) {size[x]=1;vis[x]=true;deep[x]=deep[fa[x]]+1;for(int i=head[x];i;i=edge[i].next){int to=edge[i].to;if(fa[x]!=to&&!vis[to]){fa[to]=x;dfs(to);size[x]+=size[to];}} } int dfs1(int x) {int t=0; vis[x]=true;if(!top[x]) top[x]=x;for(int i=head[x];i;i=edge[i].next){int to=edge[i].to;if(fa[x]!=to&&size[to]>size[t]) t=to;}if(t&&!vis[t]){top[t]=top[x];dfs1(t);}for(int i=head[x];i;i=edge[i].next){int to=edge[i].to;if(fa[x]!=to&&to!=t&&!vis[to])dfs1(to);} } int LCA(int x,int y) {while(top[x]!=top[y]){if(deep[top[x]]<deep[top[y]])swap(x,y);x=fa[x];}if(deep[x]>deep[y])swap(x,y);return x; } int main() {n=read();a[0]=1;for(int i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);dfs(1);memset(vis,0,sizeof(vis));dfs1(1);m=read();//a[1]=read();for(int i=1;i<=m;i++){a[i]=read();lca=LCA(a[i-1],a[i]);ans+=deep[a[i-1]]+deep[a[i]]-2*deep[lca];//printf("%d %d\n",lca,ans); }printf("%d",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/z360/p/7544527.html

總結(jié)

以上是生活随笔為你收集整理的codevs——1036 商务旅行的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。