|Online Judge||Problem Set||Authors||Online Contests||User|
The Longest Detour Problem
Let G be a weighted graph, i.e., every edge in G is associated with a nonnegative integer weight. The length of a path is the sum of edge weights in the path. A shortest path between vertices r and s in G, denoted by PG(r, s), is defined as a path with the shortest length from r to s. The distance between vertices r and s, denoted by dG(r, s), is the length of the shortest path PG(r, s). For two vertices in a connected graph, there exists at least one shortest path between them. Let e = (u, v) be an edge in PG(r, s) with v closer to s than u (v may be s). Let G - e denote the subgraph obtained by removing edge e from G. A detour from u is the shortest path from u to s in G - e, or PG-e(u, s). Edge e is a detour -critical edge in PG(r, s) if the removal of e results in the maximum distance increment from u to s. In other words, if e is a detour -critical edge in PG(r, s), then dG-e(u, s) - dG(u, s) is maximum among all edges in PG(r, s). The longest detour problem is to find the maximum distance increment of a shortest path.
Figure 4: A weighted graph G.
For example, see Figure 4. PG(4, 1) =< 4, 3, 2, 1 > is the shortest path from vertex 4 to vertex 1. Path < 4, 6, 1 > is the detour from vertex 4 to vertex 1 if edge (4, 3) is removed. Path < 3, 5, 1 > is the detour from vertex 3 to vertex 1 if edge (3, 2) is removed. Path < 2, 5, 1 > is the detour from vertex 2 to vertex 1 if edge (2, 1) is removed. The detour -critical edge in PG(4, 1) is not edge (4, 3) or edge (2, 1) but edge (3, 2) since dG-(3,2)(3, 1) - dG(3, 1) = 600 - 200 = 400 is greater than dG-(4,3)(4, 1) - dG(4, 1) = 500 - 300 = 200 and dG-(2,1)(2, 1) - dG(2, 1) = 200 - 100 = 100.
The algorithm for finding detours, as well as determining the detour-critical edges, is important from the viewpoint of network management. Due to a sudden edge failure
from some vertex, the message must be retransmitted through a detour from the vertex adjacent to the faulty edge.
Suppose that we have several networks. Each network is connected and contains at most n vertices, where 3 <= n <= 100. Assume now that you are hired to serve as a
network administrator and have to determine the maximum distance increment caused by a detour-critical edge of a given shortest path for each network.
The input consists of several test cases. The first line contains an integer indicating the number of test cases. Each test case starts with a positive integer n, where 3 <= n <= 100. The following n lines represent the adjacency matrix of a network. An adjacency matrix of a network G with n vertices, denoted by A(G) = [wu,v], is an n * n matrix such that wu,v > 0 if (u, v) is an edge of G, and wu,v= 0 otherwise, where wu,v in a nonnegative integer. Note that any two elements in each line of an adjacency matrix are separated by a space. The last line of each test case represents the sequence of vertices in a given shortest path in which there is also a space between two vertices. Note that the first and the last vertices denote the source and the destination vertices, respectively. For example, the adjacency matrix of the graph in Figure 4 is shown in test case 3 of the sample input.
For each test case, output the maximum distance increment caused by the detour-critical edge of the given shortest path in one line.
3 3 0 10 20 10 0 10 20 10 0 3 2 1 4 0 10 10 30 10 0 30 0 10 30 0 10 30 0 10 0 4 3 1 2 6 0 100 0 0 100 200 100 0 100 0 100 400 0 100 0 100 500 0 0 0 100 0 500 300 100 100 500 500 0 0 200 400 0 300 0 0 4 3 2 1
20 30 400
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator