https://www.acmicpc.net/problem/1916
initial DIJKSTRA Template
This is a typical dijkstra question but I made some careless mistakes. Pay attention to
impt) 1d Distance list tells you the distance from start node to all other nodes based on the index of that list.
1) How you are appending to your graph. Would it be a tuple? A list? My way has been a tuple always so stick to it. Also pay attention to the first index and second index. I tried appending cost and end node like heap but along the implementation, I wrongly assigned the values as end node and cost by the index. So tbs just do end node and cost
2) graph=defaultdict(list) would save you a whole lot of trouble
3) You need a separate distances list of INF because it tells you the min. Distance to every possible node from your start node. This is a clear difference from floyd where floyd is a 2d distance list that tells every min. Distance from any start node (like 1~5) to end node (1~5) but for dijkstra, you can only know from 1 specific start node (like node 3 to all other end nodes).
4) Floyd thus has greater space and time complexity
5) Dont blindly heappush (0,1) where 1 is start node of your test case. But if start node can differ for each test case, you need to push (0,start_node). Same for setting distance[1] to 0. It should be distance[start_node]=0
6) I got the dijkstra condition messed up but if cur_cost+next_cost < distance[next_node] then we do our logic. [Fix] oh but you can also do condition like if distance[cur_node] + next_cost < distance[next_node].
7) see the condition and mark graph as bidirectionally (graph[b].append((a,c))) cuz if you dont, the traversal will not go back to certain cities where it originally came from and thus cost of traversal might be bigger than answer. See this example : https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-1504%EB%B2%88-%ED%8A%B9%EC%A0%95%ED%95%9C-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C
8) remember you need to add a list as a parameter of dijkstra (or any other methods), you have to use .copy() or else you will add the reference of that object, which the object will be reused over and over when same method is called again. Look at : https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-1504%EB%B2%88-%ED%8A%B9%EC%A0%95%ED%95%9C-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C
9) IMPT: remember to optimise the time, if the distance[cur_node]<cur_distance, we dont wanna traverse the current route that we just popped from heap cuz there has already been a recorded route that is shorter
https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-5972%EB%B2%88
solution
retry with defaultdict and appending next_node, cost to graph
import heapq,sys
input = sys.stdin.readline
n = int(input())
m = int(input())
distance = [int(10e18) for _ in range(n + 1)]
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((c, b))
x, y = map(int, input().split())
heap = []
heapq.heapify(heap)
heapq.heappush(heap, [0, x])
def dijkstra(cost, node):
while heap:
cur_cost, cur_node = heapq.heappop(heap)
if distance[cur_node] < cur_cost:
continue
for hola in graph[cur_node]:
next_cost,next_node = hola
if cur_cost+next_cost < distance[next_node]:
distance[next_node] = cur_cost+next_cost
heapq.heappush(heap, (cur_cost+next_cost, next_node))
distance[x]=0
dijkstra(0,x)
print(distance[y])complexity
oh i didnt know but heap operations have log V time. So since we are doing heap on dijkstra which is v+e, the total time is v+e log v
The 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 in the graph. The log(V) factor comes from the heap operations (insertion and extraction of the minimum element).
The space complexity is O(V + E), where V is the space required to store the distances for each vertex, and E is the space required to store the graph representation (adjacency list).
In your code, you're using a heap to store vertices, so the space complexity also includes the space required for the heap, which is O(V) in the worst case.
So, to summarize:
- Time complexity: O((V + E) * log(V))
- Space complexity: O(V + E)
