2 shunfurh shunfurh 于 2017.08.29 16:58 提问

Transportation Network

A transportation network consists of a central node and some other nodes directly or indirectly (through some intermediate nodes) connected to the central node, and also the transporting channels which connect them. It is known that for any node in the transportation network there is exactly one path leads to the central. Every channel has its own length, the distance between any two nodes is defined as the total length their shortest path.

For example, in the following transportation network (the numbers in the parentheses represents the length of the channels):

  1
 /\

(2) / \ (3)
2 3
(2)| |(2)
| |
4 5

The distance between 2 and 3 is 5, the distance between 1 and 4 is 4, and the distance between 3 and 5 is 2.

Two transportation network can be combined, combining network A to network B means building a channel that connects the central of A and the central of B, and take the central of B as the central of the combined network. That combined network contains all the nodes and channels that is in network A or in network B.

Country-A has N (3 <= N <= 20,000) nodes that needs transporting between. Initially there is no channel between them, and each node is a solo transportation network. For the transporting the substance more expediently, Country-A has decided to build some transporting channels.

To maintain the information of the networks, Country-A has bought a super computer, which can receive and execute two kinds of instructions:

1) Q i j (1 <= i, j <= N, i <> j)

Querying the distance between node i and node j in the network. If they are not in the same network, output "Not connected." (Without quotation), output the distance otherwise.

2) U i j l (1 <= i, j <= N, node i and node j are not in the same network)

Combine the network containing i to the network containing j, makes the channel between them be l. (l is an integer, and 0 < l <= 1,000)
To avoid hackers' invasion which may cause the leak of the information, you should input the instruction U i' j' l instead of U i j l (where i' = (i + last_result) mod n + 1, j' = (j + last_result) mod n + 1 here last_result is the result of last valid query (i.e. the query that i and j are in the same network). Initially last_result = 0.

Your task is to write the program for the super computer.

Input

The first line of the input is an integer X (0 < X <= 6) represents number test cases of this problem. Then X blocks each represents
a test case.

The first line of each block contains two numbers N and M (5 <= M <= 40,000) representing country-A has N transportation nodes and the super computer will receive M instructions. Then M lines each represents an instruction, has the format Q i j or U i' j' l, which has been described above.

There're NO breakline between two continuous test cases.

Output

For each querying output one line an integer represents the distance or "Not connected." (Without quotation)

There're NO breakline between two continuous test cases.

Sample Input

2
4 6
U 3 4 4
Q 2 3
U 3 2 2
Q 1 2
U 2 3 1
Q 2 4
4 6
U 3 4 4
Q 2 3
U 3 2 2
Q 1 2
U 2 3 1
Q 2 4

Sample Output

4
6
7
4
6
7

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.13 08:29
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Oracle Tablespace Transportation
前提:进行表空间传输需要用户有SYSDBA的系统权限,被移动的表空间是自包含的表空间,不应有依赖于表空间外部对象的对象存在。确定是否自包含可使用系统包DBMS_TTS中的TRANSPORT_SET_CHECK过程进行检查 例如要对表空间OLTP进行传输, SQL> exec dbms_tts.transport_set_check('OLTP',true,true); PL/SQL pr
OCP 053 31.Which two statements are correct about database transportation? (Choose two.)
31.Which two statements are correct about database transportation? (Choose two.)  A. The source and target platforms must be the same  B. Redo logs, control files and temp files are also transported
Transportation Research Board论文
珍贵的TRB论文,很难得的。共享一下,交流交流。
杭电 HDU ACM Transportation (哈理工练习赛 费用流拆边)
Transportation Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2453    Accepted Submission(s): 1043 Problem Description There are N cit
C - Heavy Transportation——spfa()算法
Think: 1知识点:spfa()算法+最短路径变形 2题意:求n = 1的点到 n = n 的所有可达路径中(当前路径权值最小的)最大值 3反思:心态已乱,自己需要静下心来以下为Wrong Answer代码——题意理解错误#include <cstdio> #include <cstring> #include <queue> #include <algorithm>using names
Computer Networks (5th Edition)
The physical layer -- The data link layer -- The medium access control sublayer -- The network layer -- The transportation layer -- The application layer -- Network security.
Transportation-POJ 1040
回溯的练习题,以后少用memcpy了,复杂度haoda
HDU_3667_Transportation(最小费用流)
题意:求从城市1运送K单位物品到城市n的最小花费。给定的有向边,每条边都有其容量c,并且,产生的费用是 a * ( f * f ),其中f是这条边上的流量,a是给出的系数。 分析:这个题貌似是刘汝佳大白书当作一种典型的建图方法:拆边法。假如给定一条边(u,v),其计费系数为a,容量为c,那么可以把(u,v)拆成5条边,费用为(1a,3a,5a,7a,9a),容量都为1,为何这样子建图是有效的呢?很明显,假设流量为1,根据最短路优先原则那么肯定走的是cost=1a的那条边;若流量为2,肯定走的是cost=(
Urban Transportation Networks
sheffi经典教材英文版,学交通的必读
transit, transfer, convey->conveyance, transport->transportation
transport->transportationn.流放,放逐;流放期运输;输送convey->conveyancen.运输;搬运;表达(财产等的)转让;转让证书运输工具;交通工具;车辆transfern.迁移, 移动, 传递, 转移, 调任, 转帐, 过户, 转让vt.转移, 调转, 调任, 传递, 转让, 改变vi.转移, 转学, 换车transitn.通过;穿过;经过转运;转口;过境运输〈