Question

A kingdom has N cities with M roads between them. You are given a 2D array E

denoting that there is a road between the cities E[i][0] and E[i][1] with a distance

of E[i] [2] for all Osis N-1.

Bob loves traveling very much and wants to travel the kingdom. He can start his

trip from any city and end the trip in any city he wants. However, he can't visit the

same city more than once.

You can perform the following operation exactly once:

Take one road with its distance and delete this road. Add it in another place

where there is no road, provided that all cities remain connected each

other(you can add the road in the same place where it was removed).

Find the minimum distance of the longest trip t Bob can take after performing the

above given operation.

Note:

Its guaranteed that there is a path between every two cities.

Input Format

The first line contains an integer, N, denoting the number of cities in the kingdom.

The next line contains an integer, M, denoting the number of rows in E.

The next line contains an integer, three, denoting the number of columns in E.

Each line i of the M subsequent lines (where 0 ≤ i < M) contains three space

separated integers each describing the row E[i].

Constraints

1 <= N <= 2000

N-1 <= M <= N-1

3 <= three <= 3

1 <= E[i][j] <= 10^5

Sample Test Cases

Case 1

Input:

2

1

3

1 2 2

Output:

2

Explanation:

Given N=2,, M = 1, three = 3, E= [[1, 2, 2]].

We can remove the road between cities 1, 2 and add it in the same place. So the

minimum distance of the longest trip is 2.

Case 2

Input:

3

2

3

1 2 1

2 3 2

Output:

3

Given N=3, M=2 ,three=3,E=[[1,2,1],[2,3,2]]

We can remove the road between cities 2,3 and it between 1,

3.So the minimum distance of the longest trip is 3.

case 3

input

3

2

3

1 2 2

1 3 3

output

5

Given N=3, M = 2, three = 3, E= [[1,2,2],[1,3,3]]

We can remove the road between cities 1,2 and add 2,3. So the minimum distance

of the longest trip is 5.

Answer 1

def find_min_longest_trip(N, M, E):
from collections import defaultdict
import heapq
graph = defaultdict(list)
edges = []
# Build the graph
for u, v, w in E:
 graph[u].append((v, w))
 graph[v].append((u, w))
 edges.append((w, u, v))
# Function to find MST using Prim's algorithm
def prim_mst():
 mst_cost = 0
 visited = [False] * (N + 1)
 min_heap = [(0, 1)] # (cost, node)
 while min_heap:
 cost, node = heapq.heappop(min_heap)
 if visited[node]:
 continue
 visited[node] = True
 mst_cost += cost
 for neighbor, weight in graph[node]:
 if not visited[neighbor]:
 heapq.heappush(min_heap, (weight, neighbor))
 return mst_cost
# Compute MST cost
mst_cost = prim_mst()
# Find all edges not in MST
non_mst_edges = []
for w, u, v in edges:
 if w > mst_cost:
 non_mst_edges.append((w, u, v))
# If there are no edges not in MST, the result is the MST cos
t
if not non_mst_edges:
 return mst_cost
# Function to find minimum of maximum distances after modifyi
ng an edge
def min_longest_trip_after_modification():
 min_longest_trip = float('inf')
 for w, u, v in non_mst_edges:
 # Remove edge u-v from the graph temporarily
 graph[u] = [(nv, nw) for nv, nw in graph[u] if nv !=
v]
 graph[v] = [(nu, nw) for nu, nw in graph[v] if nu !=
u]
 # Calculate the maximum distance after this modificat
ion
 max_distance = 0
 visited = [False] * (N + 1)
 def dfs(node, distance):
 nonlocal max_distance
 visited[node] = True
 max_distance = max(max_distance, distance)
 for neighbor, weight in graph[node]:
 if not visited[neighbor]:
 dfs(neighbor, distance + weight)
 # Start DFS from any node (here 1)
 dfs(1, 0)
# Restore the graph
 graph[u].append((v, w))
 graph[v].append((u, w))
 # Update min_longest_trip
 min_longest_trip = min(min_longest_trip, max_distanc
e)
 return min_longest_trip
# Find the minimum of the maximum distances
result = min_longest_trip_after_modification()
return result