We have been given a graph such that a path exists between any two given nodes.The edges have some weight assigned to them. We are given a starting node and a ending node and we required to find the minimum distance between two nodes.The distance is the sum of edge weights. We have a special power by which we can change the weights of atmost k edges, we can make their weight to be equal to zero. So given two nodes we are supposed to find the minimum distance between them using the special power atmost k times.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:09:16
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:09:16
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 10:25:44 (j3).
Десктопная версия, переключиться на мобильную.
При поддержке
Can you provide the link to the original problem?
Graph is a tree => unique path between any 2 nodes. You just need to determine the path between the given nodes and take the weight of k "heaviest" edges in the path to be 0.
First root the tree on any one vertex
UorVthen find the parent arrayp[i]then you can traverse from U to V and then make all heaviestKedges equal to zero and find the sum of remaining edges.Consider an example graph- (1 2 2), (1 3 2), (2 4 2), (4 5 1), (3 5 7), Consider it as (u,v,w) i.e. edge between u and v with weight w. And also suppose k=1 and we need path from node 1 to node 5. Now can you tell what will be the correct approach according to this example. All edges are undirected.
Auto comment: topic has been updated by hardy_9795 (previous revision, new revision, compare).
The graph was not a tree sorry for the mistake.Now can someone tell the approach.It is guaranteed that there is a path between the two required nodes.
This is why you provide a link to the original problem.
Actually i don't have the link as it was part of an internship exam and we were not supposed to take the screenshots.
Sorry! Wrong approach
Consider a graph where there is a path of k+1 edges of weight 1 from the source to the destination, and also an edge from the source to the destination of weight k+2. In this graph your approach will pick the path of k+1 edges, ignore k of them, so the cost will be equal to 1. But it is optimal to set the weight of the heaviest edge to 0, so that the minimal cost is equal to 0.
Yes,this is the same mistake that was present in my solution also.Can you tell the correct way of solving this problem.
Oh my, you are right! I didn't think of that.
I implemented the same solution but it will fail. Consider an example graph- (1 2 2), (1 3 2), (2 4 2), (4 5 1), (3 5 7), Consider it as (u,v,w) i.e. edge between u and v with weight w. And also suppose k=1 (the no. of times we can use the special power) and we need path from node 1 to node 5. Now can you tell what will be the correct approach according to this example. All edges are undirected. In this example the correct answer is 2 but your logic will give 3.
I don't really know how to solve this if V, E and K are relatively big, but i have an idea that works in O((V+E)*K*log(V)).
If k=0, we just use dijkstra to generate the array dist[x] and the answer is dist[destination]. For k>0, let's give the array dist a second dimension, so that dist[x][y] represents the shortest path to x from the source, which sets the weight of y edges to zero. Now the answer for our problem is the minimum of all dist[destination][y]. We can calculate this array with a modified dijkstra, because now if we are currently in a node x to which we got by setting y edges to 0, for each outgoing edge to a node z we have two options:
we don't set this edge weight to 0, in this case we will change dist[z][y]
or we set this edge weight to 0, so we change dist[z][y+1]
You can think of this as duplicating the original graph into k+1 layers, and for each edge, adding an edge of cost 0 from each layer i to i+1, in this way if we calculate the shortest path from the source in layer 0, to the destinations in each layer, we will get the shortest paths that set 0, 1, 2 . . . k edges to 0.