POJ 1986 Distance Queries 【输入YY && LCA(Tarjan离线)】
2024-09-07 19:03:39
任意门:http://poj.org/problem?id=1986
Distance Queries
Time Limit: 2000MS | Memory Limit: 30000K | |
Total Submissions: 16648 | Accepted: 5817 | |
Case Time Limit: 1000MS |
Description
Farmer John's cows refused to run in his marathon since he chose a path much too long for their leisurely lifestyle. He therefore wants to find a path of a more reasonable length. The input to this problem consists of the same input as in "Navigation Nightmare",followed by a line containing a single integer K, followed by K "distance queries". Each distance query is a line of input containing two integers, giving the numbers of two farms between which FJ is interested in computing distance (measured in the length of the roads along the path between the two farms). Please answer FJ's distance queries as quickly as possible!
Input
* Lines 1..1+M: Same format as "Navigation Nightmare"
* Line 2+M: A single integer, K. 1 <= K <= 10,000
* Lines 3+M..2+M+K: Each line corresponds to a distance query and contains the indices of two farms.
Output
* Lines 1..K: For each distance query, output on a single line an integer giving the appropriate distance.
Sample Input
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6
1 4
2 6
Sample Output
13
3
36
Hint
Farms 2 and 6 are 20+3+13=36 apart.
题意概括:
输入:
第一行输入结点数 N 和 边数 M。
接下来 M 行输入边的信息:起点 u 终点 v 距离 w 方向 s
输入查询数 K
接下来 K 行 输入查询值: 起点 u,终点 v;
解题思路:
一个有向无环图,当作一棵树来处理,根结点随意,假设为 1;
LCA 两点最短距离 老套路。
AC code:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int MAXN = 5e5+;
struct Edge{int v, w, nxt;}edge[MAXN<<];
struct Query
{
int v, id;
Query(){};
Query(int _v, int _id):v(_v),id(_id){};
};
vector<Query> q[MAXN]; int head[MAXN], cnt;
int dis[MAXN];
int fa[MAXN];
bool vis[MAXN];
int ans[MAXN];
int N, M, K; void init()
{
memset(vis, false, sizeof(vis));
memset(head, -, sizeof(head));
memset(dis, , sizeof(dis));
memset(ans, , sizeof(ans));
for(int i = ; i <= N; i++) q[i].clear();
cnt = ;
} int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);} void AddEdge(int from, int to, int weight)
{
edge[cnt].v = to;
edge[cnt].w = weight;
edge[cnt].nxt = head[from];
head[from] = cnt++;
} void dfs(int s, int f)
{
int root = s;
for(int i = head[s]; i != -; i = edge[i].nxt){
if(edge[i].v == f) continue;
dis[edge[i].v] = dis[root] + edge[i].w;
dfs(edge[i].v, s);
}
} void Tarjan(int s, int f)
{
int root = s;
fa[s] = s;
for(int i = head[s]; i != -; i = edge[i].nxt){
int Eiv = edge[i].v;
if(Eiv == f) continue;
Tarjan(Eiv, root);
fa[getfa(Eiv)] = root;
}
vis[s] = true;
for(int i = ; i < q[s].size(); i++){
if(vis[q[s][i].v] && ans[q[s][i].id] == ){
ans[q[s][i].id] = dis[q[s][i].v] + dis[s] - *dis[getfa(q[s][i].v)];
}
}
} int main()
{
scanf("%d%d", &N, &M);
init();
char s;
for(int i = , u, v, w; i <= M; i++){
scanf("%d%d%d %c", &u, &v, &w, &s);
AddEdge(u, v, w);
AddEdge(v, u, w);
}
scanf("%d", &K);
for(int i = , u, v; i <= K; i++){
scanf("%d%d", &u, &v);
q[u].push_back(Query(v, i));
q[v].push_back(Query(u, i));
}
dfs(, -);
Tarjan(, -);
for(int i = ; i <= K; i++){
printf("%d\n", ans[i]);
}
return ;
}
最新文章
- Hyper-V 激活Windows系统重启后黑屏的解决方法 + 激活方法
- 禁用datagridview中的自动排序功能
- (python) 标准模块sys和os的使用
- 2015年免费的25款 WordPress 网站模板
- 织梦DEDECMS网站后台安全检测提示 加一个开关
- js 模拟ajax方式提交数据
- iOS 隐藏Status Bar
- I.MX6 AT24Cxx eeprom Linux i2c-gpio
- MySQL优化---DBA对MySQL优化的一些总结
- SQL SERVER 2008查询其他数据库
- C++Primer笔记二
- 一劳永逸让windows 64位操作系统 禁止强制驱动签名
- STM32电源管理
- 嵌入javascript脚本的位置
- .NET Core 微服务架构 Steeltoe 使用(基于 Spring Cloud)
- 多个yml文件的读取方式
- Browser Page Parsing Details
- java.lang.RuntimeException: Unable to instantiate org.apache.hadoop.hive.metastore.HiveMetaStoreClient
- js数组排序实用方法集锦
- NOI 2016 区间 解题报告
热门文章
- QiyeProject SpringMVC 项目 d15866p148.iok.la 主要做主页应用,消息应用不管了 用户微信号有点像乱码的那个是openID 找同伴:在项目的GitHub页面里找提问过的人,还有fork,star的人
- oracle 操作实例(一)----redolog 损坏恢复
- 测试次数(C++)
- Beam编程系列之Apache Beam WordCount Examples(MinimalWordCount example、WordCount example、Debugging WordCount example、WindowedWordCount example)(官网的推荐步骤)
- unity5.5 5.6 使用c#6.0或7.0
- lua ";诡异";的return用法
- mongodb连接失败原因排查
- jqGrid -treeGrid 按需加载
- HyperLink 控件
- 1.zookeeper的安装