peacebringer167's blog

By peacebringer167, history, 2 years ago, In English

In an undirected graph, we define that the cost of a path is the minimum value of AN EDGE that lies in the path. For example, there is a path like this: 1->2->4, and the weight of the edge between (1,2),(2,4) are 9 and 13 consecutively, so the cost of this path is 9. Consider the cost of two vertices (u,v), in every path that connects u and v, choose the path that has the highest cost, and that cost is the cost of (u,v).
For example, we have this graph:
https://ibb.co/tmg1xkN
The cost of 1 and 4 is 10, there are 2 paths, 1->2->4 (cost 10) and 1->3->4 (cost 5) so the cost is 10 Given an undirected graph, find the cost between 1 and all other vertices from 2 to N, with N <= 10^5, and the number of edges is smaller than 5.10^6

Can anyone please help me with this? What type of problem is this? Many thanks in advance!!! (Also, pardon me because of my bad English)

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by peacebringer167 (previous revision, new revision, compare).