Given a weighted directed graph. Consider a vertice u connected to v1, v2, v3, ... with weight w1, w2, w3,.. You may permute the weight in any way you like. Ex: Edges from u are initially (u, v1, w1), (u, v2, w2), (u, v3, w3).. You can change it to (u, v1, w3), (u, v2, w1), (u, v3, w2). The weight must be permuted before the journey and remain that way through out the journey. Find the largest possible shortest path from 1 to n. Constraints: n <= 1e5, m <= 3e5 u , v <= n w <= 1e6 It sounds really cool but I have no idea how to solve it. Can someone help? Thanks :))
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 151 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 08:27:21 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
This problem cam be solved on a DAG. Just do the basic dp. On a regular graph, I think you can do the same dp but with Dijkstra like algorithm where you go and calculate dp values from lowest to highest. Not sure how to avoid that going to O(N^2) or worse, but it might be possible.