Connections between cities
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5067 Accepted Submission(s): 1410
Problem Description
After World War X, a lot of cities have been seriously damaged, and we need to rebuild those cities. However, some materials needed can only be produced in certain places. So we need to transport these materials from city to city. For most of roads had been totally destroyed during the war, there might be no path between two cities, no circle exists as well.
Now, your task comes. After giving you the condition of the roads, we want to know if there exists a path between any two cities. If the answer is yes, output the shortest path between them.
Now, your task comes. After giving you the condition of the roads, we want to know if there exists a path between any two cities. If the answer is yes, output the shortest path between them.
Input
Input consists of multiple problem instances.For each instance, first line contains three integers n, m and c, 2<=n<=10000, 0<=m<10000, 1<=c<=1000000. n represents the number of cities numbered from 1 to n. Following m lines, each line has three integers i, j and k, represent a road between city i and city j, with length k. Last c lines, two integers i, j each line, indicates a query of city i and city j.
Output
For each problem instance, one line for each query. If no path between two cities, output “Not connected”, otherwise output the length of the shortest path between them.
Sample Input
5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5
Sample Output
Not connected
6
Hint
Hint Huge input, scanf recommended.
题意:
给出 N 个结点,M 条边,K 个询问。输出每个询问间的距离,如果不能达到的话则输出 Not connected。
思路:
LCA + 并查集。用并查集判断是否在同一棵上,在同一棵树上则用 LCA 算出距离即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int NMAX = 10010; const int EMAX = 10000 * 5; int n, m, c; int root[NMAX]; int ind; int fir[NMAX], next[EMAX], w[EMAX], v[EMAX]; int ans; int id[NMAX], vs[NMAX * 3], dep[NMAX * 3], dis[NMAX]; bool vis[NMAX]; int dp[NMAX * 3][50]; void init () { ind = ans = 0; memset(fir, -1, sizeof(fir)); memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; ++i) root[i] = i; } void add_edge (int f, int t, int val) { v[ind] = t; w[ind] = val; next[ind] = fir[f]; fir[f] = ind; ++ind; } int Find (int x) { return x == root[x] ? x : root[x] = Find(root[x]); } void merge_tree (int a, int b) { int A = Find(a); int B = Find(b); if (A != B) root[A] = B; } bool que_tree (int a, int b) { if (Find(a) == Find(b)) return true; return false; } void dfs (int x, int d) { id[x] = ans; vs[ans] = x; dep[ans++] = d; vis[x] = 1; for (int e = fir[x]; e != -1; e = next[e]) { int V = v[e]; if (!vis[V]) { dis[V] = dis[x] + w[e]; dfs(V, d + 1); dep[ans] = d; vs[ans++] = x; } } } void RMQ_init () { for (int i = 0; i < ans; ++i) dp[i][0] = i; for (int j = 1; (1 << j) <= ans; ++j) { for (int i = 0; i + (1 << j) < ans; ++i) { int a = dp[i][j - 1]; int b = dp[i + (1 << (j - 1))][j - 1]; if (dep[a] < dep[b]) dp[i][j] = a; else dp[i][j] = b; } } } int RMQ (int L, int R) { int len = 0; while ((1 << (len + 1)) <= (R - L + 1)) ++len; int a = dp[L][len]; int b = dp[R - (1 << len) + 1][len]; if (dep[a] < dep[b]) return a; return b; } int LCA (int a, int b) { int L = min(id[a], id[b]); int R = max(id[a], id[b]); int node = RMQ(L, R); return vs[node]; } int main() { while (~scanf("%d%d%d", &n, &m, &c)) { init(); while (m--) { int a, b, val; scanf("%d%d%d", &a, &b, &val); add_edge(a, b, val); add_edge(b, a, val); merge_tree(a, b); } for (int i = 1; i <= n; ++i) { if (root[i] == i) { dis[i] = 0; dfs(i, 1); } } RMQ_init(); while (c--) { int a, b; scanf("%d%d", &a, &b); if (que_tree(a, b)) { int c = LCA(a, b); printf("%d\n", dis[a] + dis[b] - 2 * dis[c]); } else puts("Not connected"); } } return 0; }
相关推荐
NATBLASTER-Establishing TCP Connections Between Hosts Behind NATs.pdf
We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer ...
IBM connections5.5 性能调优 connections性能优化。 http server WAS oracle db2 优化。
informatica Windows下配置connections的简单例子
IBM Connections 4.0 新特性&演示
lotus Connections企业级部署
mysql官方告诉我们需要修改max_connections的值,那么我们怎么去修改呢?有两种方法 1、修改配置文件文件 修改/etc/my.cnf这个文件,在[mysqld]中新增max_connections=N,如果你没有这个文件请从编译源码中的support...
IBM Access Connections 3.71 经典的网络连接工具
Lenovo(IBM)出品的Access Connections是一款功能强大的网络辅助软件。 现如今毫无疑问的我们已经进入了网络互联时代,而对于笔记本这种移动设备来说就需要经常在各种不同的网络环境下使用,比如在公司需要根据...
在mysql的手册中已经对max_user_connections有一点说明,它是用来限制用户资源的,怎么限制用户资源呢?这里做了个小测试。首先产看该全局变量的值mysql> select @@max_user_connections;+————————+| @@max_...
IBM Connections 3 是专门为满足业务需求而设计的一款社交软件。它能帮助商业人士组建主题专家网络,让他们更具创新力和生产力。它能促进创建由员工、合作伙伴和客户组成的活力社区,交换有创造力的想法,帮助不断...
Laravel开发-laravel-connections 这个软件包使雄辩的模型能够管理他们的友谊。
图解 Tomcat maxConnections、maxThreads、acceptCount
It offers unsurpassed features designed to illuminate connections between pharmacology and practice, from patient scenarios and practice applications to coverage of lifespan considerations, patient ...
IBM的Access Connections软件是一款功能强大的网络辅助软件。现如今毫无疑问的我们已经进入了网络互联时代,而对于笔记本这种移动设备来说就需要经常在各种不同的网络环境下使用,比如在公司需要根据网络环境设置...
labviewTCP Multiple Connections - Client 1
Telerik.NetworkConnections.Windows.dll
监控安卓手机应用网络连接状况,并记录相应日志。
最近在项目中遇到一个问题,由于连接数过多,提示 “Too many connections” ,需要增加连接数。 我在 /etc/my.cnf中修改了: max_connections = 2000 但是, 实际连接数一直被限制在 214: mysql> show variables ...
显著度图 of Deeply Supervised Salient Object Detection with Short Connections, ECSSD数据集