Need help in this problem.

Правка en3, от minhi1, 2024-01-21 13:00:00

Given a connected graph with n nodes and m edges (n, m <= 1e5). There are q queries (q <= 1e5), each has type of (u, d, c) means to color all nodes which have the smallest distance to u <= d color c (d <= 10, c <= 1e5). What is the color of n nodes after q queries.

I can only do smaller subtask when n,m,q <= 2000 with bfs. I do think about solving queries backward and color nodes that are empty but still don't know how to optimize it. Can anyone help me. Thanks.

Теги graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский minhi1 2024-01-21 13:00:00 0 (published)
en2 Английский minhi1 2024-01-21 12:53:47 126 (saved to drafts)
en1 Английский minhi1 2024-01-21 12:53:25 623 Initial revision (published)