choutii's blog

How to solve this problem BAEKJOON Online Judge 8452
By choutii, history, 7 years ago, In English

https://www.acmicpc.net/problem/status/8452

the problem is

A directional graph G is given. When the length of all trunks is 1, you must process two queries.

  1. Remove one trunk.
  2. Outputs the shortest path from vertex 1 to vertex i. If there is no path, -1 is output.

|V| <= 10^3, M, Q <= 10^5

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Rather than removing edge, we will define cost to an edge, which is either infinity or the time of edge removal.

Now make a DP table analogous with Bellman-Ford. (dp[i][j] = min cost over all edges, for all path 1 ~ i of length <= j). Respond every query by binary search.

→ Reply