谭松松的旅游计划

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Submit Status

谭松松是一个爱旅游的人，他非常的热爱旅游，即便身体被掏空也要坚持旅游。喵蛤王国由N个城市组成，由N-1条道路连通，每条道路长度为ci,使得任意两座城市都能相互到达。谭松松有M个旅游计划，每个旅游计划有一个起点ai,一个终点bi,所以谭松松想知道，对于每个旅游计划，从起点到终点的最短路长度为多少？

Input

第一行两个整数N(2≤N≤100000，)，M(1≤M≤100000)，表示城市个数，谭松松的旅游计划个数。

接下来N-1行，每行三个整数li,ri,ci（1≤ci≤10000），表示li号城市和ri号城市之间有一条长度为ci的道路。

接下来M行，每行两个整数ai,bi表示旅游计划的起点和终点。

Output

输出M行，表示每个旅游计划的最短距离。

Sample input and output

Sample Input	Sample Output
7 6 1 2 5 1 3 4 3 7 7 2 4 4 2 5 3 5 6 2 1 2 4 7 6 3 3 2 5 4 7 6	5 20 14 9 7 21

代码

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define ll long long

 const int MAXN=;

 using namespace std;

 int N,M;

 int pa[][MAXN],depth[MAXN],vis[MAXN];

 ll cost[][MAXN];//注意long long

 vector<int> G[MAXN],c[MAXN];

 void dfs(int x,int pre,int d){

     vis[x]=;

     depth[x]=d;

     pa[][x]=pre;

     for(int i=;i<G[x].size();i++){

         int to=G[x][i];

         if(!vis[to]){

             cost[][to]=c[x][i];

             dfs(to,x,d+);

         }

     }

 }

 void init_lca(){

     memset(pa,-,sizeof(pa));

     dfs(,-,);

     for(int k=;k<=;k++){

         for(int i=;i<=N;i++){

             if(pa[k][i]>){

                 pa[k+][i]=pa[k][ pa[k][i] ];

                 cost[k+][i]=cost[k][i]+cost[k][ pa[k][i] ];

 //                cout<<cost[k+1][i]<<endl;

             }

         }

     }

 }

 ll lca(int u,int v){//long long

     ll sum=;

     if(depth[u]>depth[v]) swap(u,v);

 //    cout<<u<<v<<endl;

     for(int k=;k<;k++){

         if((depth[v]-depth[u])>>k&){

             sum+=cost[k][v];

             v=pa[k][v];//这两行不能换.....

 //            cout<<cost[k][u]<<endl;

         }

     }

     if(u==v) return sum;

     for(int k=;k>=;k--){

         if(pa[k][u]!=pa[k][v]){

             sum+=(cost[k][u]+cost[k][v]);

             u=pa[k][u];

             v=pa[k][v];

         }

     }

     sum+=(cost[][v]+cost[][u]);

     return sum;

 }

 int main(){

 //    freopen("01.in","r",stdin);

     scanf("%d%d",&N,&M);

     for(int i=;i<N;i++){

         int x,y,cc;

         scanf("%d%d%d",&x,&y,&cc);

         G[x].push_back(y);

         G[y].push_back(x);

         c[x].push_back(cc);

         c[y].push_back(cc);

     }

     init_lca();

     while(M--){

         int a,b;

         scanf("%d%d",&a,&b);

         printf("%lld\n",lca(a,b));//此处用cout会T!!!

     }

     return ;

 }

Line50 和Line51换了会爆炸

然后83用cout会爆炸，直接T掉

输出1万次就得用printf

cout也就比printf慢几千倍吧~

巴特西

CDOJ 1437 谭松松的旅游计划 Label:倍增LCA && 最短路

谭松松的旅游计划

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Input

Output

Sample input and output

代码

最新文章

热门文章