[백준] 1238번: 파티

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

initial

In this question we want to find the longest duration for a round-trip from any city to that party city and back. We cannot use a floyd warshall cuz n is up to 1000 so 1000x1000 matrix is gonna cause runtime. So use dijkstra. We initialise answer list of 0s and each index represents the cost to travel to that party city and back.

1) Dijkstra from all the cities to that party city and add that specific distance (by accessing index of party city) to the answer list’s iter start city. So effectively here we add just 1 value

2) Dijkstra from party city to all the other cities for the round trip cost. Here we add all values of that distance list to the answer list because we need to add all the round trip costs no matter whichever the city.

but actually we dont have to perform dijkstra for every node, as i will explain later below

my solution 1200 ms (ineff)

im not sure why this is 1200ms and below is 50ms considering it is similar approach

maybe cuz 1) im using double for loop

[Fix] No it is not that. What exactly does dijkstra do? It tells the minimum distance from a specific start node to all other nodes via a 1d list. I thus iterated through all the nodes from 1 to n to calculate the distance from all nodes to that party city.

HOWEVER, there is a more clever way that we dont have to do dijkstra on each node. IF we reverse the direction from initial a->b to b->a, then effectively if we do dijkstra on party node, it tells us the min. Cost to reach the party node. Lets slow down. If we marked graph as a->b direction, then dijkstra tells us the min distance from a specific node to reach that party node. But if we mark it the reverse way, then dijkstra tells us the min distance to reach a specific node from party node.**. (cuz the directions have been reversed). So we can just perform dijkstra twice. This is very clever.

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

n, m, x = map(int, input().split())
graph = defaultdict(list)

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

def dijkstra(node, distance):
    heap = []
    heapq.heappush(heap, (0, node))
    
    while heap:
        cur_cost, cur_node = heapq.heappop(heap)
        
        for next_node, next_cost in graph[cur_node]:
            # optimization to skip unnecessary iterations
            if distance[cur_node] < cur_cost:
                continue
            
            if cur_cost + next_cost < distance[next_node]:
                distance[next_node] = cur_cost + next_cost
                heapq.heappush(heap, (cur_cost + next_cost, next_node))

    return distance

ans = [0] * (n + 1)

for i in range(1, n + 1):
    tmp = [float('inf')] * (n + 1)
    tmp[i]=0
    tmp[0]=0
    hola = dijkstra(i, tmp)
    if i == x:
        for j in range(len(hola)):
            ans[j] += hola[j]
    else:
        ans[i] += hola[x]

print(max(ans))

more concise 50ms

same approach but more concise and 50ms

he made a separate graph for that reverse way traversal so he doesnt have to use a double for loop cuz he can just add the results by index

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()
import heapq

def solution (data) :
  arr = [list(map(int, x.split())) for x in data]
  n,m,x = arr.pop(0)
  
  graph = [[] for _ in range(n+1)]
  reverseGraph = [[] for _ in range(n+1)]
  for s,e,w in arr : 
    graph[s].append((w,e))
    reverseGraph[e].append((w,s))
  
  dp = dijkstra(graph, x)
  reverseDp = dijkstra(reverseGraph, x)
  result = 0
  for i in range(n) :
    result = max(result, dp[i] + reverseDp[i])

  print(result)

def dijkstra (graph,start) :
  dp = [float('inf') for _ in range(len(graph))]
  dp[start] = 0
  pq = []
  heapq.heappush(pq, (dp[start], start))
  
  while pq :
    wei, node = heapq.heappop(pq)
    if wei > dp[node] : continue
    
    for n_wei, n_node in graph[node] :
      total_wei = wei + n_wei
      if dp[n_node] > total_wei :
        dp[n_node] = total_wei
        heapq.heappush(pq, (total_wei, n_node))
  
  return dp[1:]

solution(input_data)

complexity mine

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

Time Complexity:

• The main loop iterates over all nodes (i from 1 to n), and within each iteration, it calls the dijkstra function.
• The dijkstra function has a time complexity of O((V + E) * log(V)), where V is the number of vertices and E is the number of edges. In this case, V is n and E is m.
• So, the overall time complexity is O(n (n + m) log(n)).

Space Complexity:

• The primary data structure is the heap used in the dijkstra function, which can have a maximum size of O(V) in the worst case.
• The tmp list is created for each node, but it is overwritten in each iteration and is not stored permanently. Therefore, its space complexity is O(n).
• The ans list has a space complexity of O(n + 1).
• The overall space complexity is O(n + V), where V is the maximum heap size.

In summary, the time complexity is O(n (n + m) log(n)), and the space complexity is O(n + V).

complexity of 50ms

oh this guy is not doign dijkstra for each node cuz he just reveresed the graph

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

Time Complexity:

• The primary operation is the Dijkstra's algorithm implemented in the dijkstra function.
• The while loop in the dijkstra function iterates over the priority queue, and the overall time complexity of Dijkstra's algorithm is O((V + E) * log(V)), where V is the number of vertices and E is the number of edges.
• The for loop in the solution function iterates over each node in the graph, and within each iteration, it calls the dijkstra function.
• So, the overall time complexity is O((V + E) * log(V)), where V is the number of vertices and E is the number of edges.

Space Complexity:

• The main data structures are the graph, reverseGraph, dp, and pq.
• The space complexity of graph and reverseGraph is O(V + E), where V is the number of vertices and E is the number of edges.
• The dp list has a space complexity of O(V), where V is the number of vertices.
• The priority queue pq can have a maximum size of O(E), where E is the number of edges.
• The overall space complexity is O(V + E).

In summary, the time complexity is O((V + E) * log(V)), and the space complexity is O(V + E).