[백준] 1939번: 중량제한

https://www.acmicpc.net/problem/1939

This is a really good DS question.
sample test cases:

3 4
1 2 2
1 2 2
3 1 3
2 3 2
1 3

5 4
1 2 3
2 3 4
1 5 6
3 5 7
1 5
ans =6

initial

So if there are multiple bridges, we just add the total weight that can be withstood when travelling from city a to city b. As we traverse with dfs, we only traverse paths where cost isnt 0 (so there should be a bridge in between) and when current cost is 4, and current bridge can only carry cost of 2, we have to take the min() of the 2 costs, which is 2. I looked for all paths that we can take from start city node

my correct but runtime and memory prob solution:

import sys
input = sys.stdin.readline
from collections import defaultdict, deque

n, m = map(int, input().split())
graph = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a][b]+=c
    graph[b][a]+=c
start,end = map(int,input().split())
# print(graph)
ans=0

def dfs(node,cost):
    global ans
    if node==end:
        ans = max(cost,ans)
        return
    for i in range(1,n+1):
        if graph[node][i]==0:
            continue
        if not visited[i]:
            # if graph[node][i]<cost:
            cost=min(cost,graph[node][i])
            visited[i]=True
            dfs(i,cost)
for i in range(1,n+1):
    if graph[start][i]==0:
        continue
    visited= [False for _ in range(n+1)]
    visited[start]=True
    dfs(i,graph[start][i])

print(ans)

solution

so since it is gold 3 we need to upgrade code with binary search

First, the memory issue can be improved by making a 2d adj list like that but wait isnt it the same? tbc

but continuing,
binary search well-explained:
https://www.acmicpc.net/blog/view/109

so as we rmb BS is used to literally guess our answer. So we use BS's mid to guess the max weight that is possible to be carried for start to end city nodes.

We are gonna input that mid value, which is our guess for max cost, inside our dfs function. If the next node is not visited and if next cost is greater than or equal to this guess, then we can take that path. Note this logic of if next cost is greater or equal is literally opposite of my initial logic where my initial solution of doing dfs tried to find the minimum cost possible to traverse from start to end node.

The logic is opposite because with BS, we are finding the maximum valid path. If our guess value is less than the weight of bridge then that is valid. Only when our guess value is too greedily big and fat and is bigger than weight of bridges and future bridges, that is invalid.

For example,
1. Initial Call to DFS:
Start Node: Start at node start (e.g., node 1).
Current Threshold (mid = 8):
Examine all neighbors of start.
Traverse only edges with weights ≥ 8.
2. Traverse Valid Edges:
Edge 1: 1 --(10)-- 2 → Valid (10 >= 8).
Mark node 2 as visited and recurse into dfs(2, mid).
3. Next DFS Step:
Current Node: Node 2.
Threshold (mid = 8):
From node 2, consider all its neighbors.
Traverse only edges with weights ≥ 8.
Edge: 2 --(15)-- 3 → Valid (15 >= 8).
Mark node 3 as visited and recurse into dfs(3, mid).

And as with dfs, your recursion end condition must be placed first. So if that end condition is met, we have a valid path. So if our dfs returns True, we return True until our starting point, traversing back the call stack. And even after traversing all options in our graph via that for loop of (next_city,next_cost) and we still cant retunn True, we return False, saying there is no valid path, in which case we have to shift our right to the left cuz our mid guess value is greedily too big and fat for our bridges to withstand.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))
start,end = map(int,input().split())

def dfs(node,cost):
    if node==end:
        return True
    for next_city,next_cost in graph[node]:
        if not visited[next_city] and next_cost>=cost:
            visited[next_city]=True
            if dfs(next_city,cost):
                return True
    return False

left,right=1,int(10e9)
while left<right:
    mid = left + (right-left)//2
    visited= [False for _ in range(n+1)]
    visited[start]=True
    if dfs(start,mid):
        left=mid+1
    else:
        right=mid
print(left-1)

bfs way

it can be solved via bfs too

complexity

Let's analyze the time and space complexity of your code:

Time Complexity:

1. Graph Initialization:

   • Creating the adjacency list takes (O(m)) time, where (m) is the number of edges.

2. Binary Search Loop:

   • The binary search loop runs in (O(\log \text{{range}})) time, where (\text{{range}}) is the range of possible values for mid (in this case, (10^9)).

3. DFS:

   • The DFS function visits each node and edge at most once, and its time complexity is (O(V + E)), where (V) is the number of vertices and (E) is the number of edges. In this case, (V) is (n) and (E) is (m).

4. Overall Time Complexity:

   • The overall time complexity is dominated by the binary search loop and the DFS operations, resulting in (O(\log \text{{range}} + V + E)).

Space Complexity:

1. Graph Representation:

   • The adjacency list representation of the graph takes (O(V + E)) space.

2. DFS Recursive Call Stack:

   • The depth of the recursion in the DFS function is bounded by the number of vertices, and the space complexity of the recursive call stack is (O(V)).

3. Visited Array:

   • The visited array has a space complexity of (O(V)).

4. Binary Search Variables:

   • The variables used in the binary search loop (left, right, mid) contribute to constant space, resulting in (O(1)) space complexity.

5. Overall Space Complexity:

   • The overall space complexity is dominated by the graph representation and the DFS recursive call stack, resulting in (O(V + E)).

Summary:

The time complexity is (O(\log \text{{range}} + V + E)), and the space complexity is (O(V + E)), where (V) is the number of vertices, (E) is the number of edges, and (\text{{range}}) is the range of possible values for mid in the binary search. The dominant factor is the DFS operation, and the binary search contributes logarithmic complexity.