xtu summer individual 1 C - Design the city
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%lld & %llu
Description
Cerror is the mayor of city HangZhou. As you may know, the traffic system of this city is so terrible, that there are traffic jams everywhere. Now, Cerror finds out that the main reason of them is the poor design of the roads distribution, and he want to change this situation.
In order to achieve this project, he divide the city up to N regions which can be viewed as separate points. He thinks that the best design is the one that connect all region with shortest road, and he is asking you to check some of his designs.
Now, he gives you an acyclic graph representing his road design, you need to find out the shortest path to connect some group of three regions.
Input
The input contains multiple test cases! In each case, the first line contian a interger N (1 < N < 50000), indicating the number of regions, which are indexed from 0 to N-1. In each of the following N-1 lines, there are three interger Ai, Bi, Li (1 < Li < 100) indicating there's a road with length Li between region Ai and region Bi. Then an interger Q (1 < Q < 70000), the number of group of regions you need to check. Then in each of the following Q lines, there are three interger Xi, Yi, Zi, indicating the indices of the three regions to be checked.
Process to the end of file.
Output
Q lines for each test case. In each line output an interger indicating the minimum length of path to connect the three regions.
Output a blank line between each test cases.
Sample Input
4
0 1 1
0 2 1
0 3 1
2
1 2 3
0 1 2
5
0 1 1
0 2 1
1 3 1
1 4 1
2
0 1 2
1 0 3
Sample Output
3
2 2
2 解题:LCA算法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxv = ;
const int maxn = ;
struct arc{
int to,w;
};
struct Q{
int index,v;
};
vector<arc>g[maxv];
vector<Q>qy[maxn];
int ans[maxn],uf[maxv],dis[maxv],n,m;
bool vis[maxv];
int _find(int x){
if(uf[x] != x)
uf[x] = _find(uf[x]);
return uf[x];
}
void dfs(int u){
vis[u] = true;
uf[u] = u;
int i,j,k,v;
for(i = ; i < qy[u].size(); i++){
v = qy[u][i].v;
if(vis[v])
ans[qy[u][i].index] += dis[u]+dis[v]-*dis[_find(v)];
}
for(i = ; i < g[u].size(); i++){
v = g[u][i].to;
if(!vis[v]){
dis[v] = dis[u]+g[u][i].w;
dfs(v);
uf[v] = u;
}
}
}
int main(){
int i,j,u,v,w,t = ;
while(~scanf("%d",&n)){
if(t) printf("\n");
for(i = ; i <= n; i++){
g[i].clear();
qy[i].clear();
uf[i] = i;
vis[i] = false;
}
for(i = ; i < n; i++){
scanf("%d%d%d",&u,&v,&w);
g[u].push_back((arc){v,w});
g[v].push_back((arc){u,w});
}
scanf("%d",&m);
for(i = ; i <= m; i++){
scanf("%d %d %d",&u,&v,&w);
qy[u].push_back((Q){i,v});
qy[v].push_back((Q){i,u});
qy[u].push_back((Q){i,w});
qy[w].push_back((Q){i,u});
qy[v].push_back((Q){i,w});
qy[w].push_back((Q){i,v});
}
memset(ans,,sizeof(ans));
dis[] = ;
dfs();
for(i = ; i <= m; i++)
printf("%d\n",ans[i]>>);
t++;
}
return ;
}
最新文章
- 便于开发的Helper类
- 流的文件操作(File)
- Sqlserver 如何获取每组中的第一条记录
- JavaScript返回上一页代码区别
- 关于出现 org.apache.commons.lang.exception.NestableRuntimeException的解决方法
- 测试驱动开发(TDD)的思考
- awk 统计数据在文件中的出现次数
- python中的静态方法和类方法
- 华为章宇:如何学习开源项目及Ceph的浅析
- php 实现文件下载,兼容IE、Firefox、Chrome等浏览器
- 转载 SharePoint Foundation和SharePoint Server的区别
- 高效实现 std::string split() API
- Windows服务器Pyton辅助运维--01.自动Copy文件(文件夹)到远程服务器所在目录
- HDU 3613 Best Reward 正反两次扩展KMP
- SQL Server 如何读写数据
- 2017年第六届数学中国数学建模国际赛(小美赛)C题解题思路
- AtCoder Regular Contest 075
- CF Good Bye 2018
- object detection[NMS]
- 【Maven】Select Dependency 无法检索