|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
18.04.2024, 13:36 | #1 |
Регистрация: 06.04.2024
Сообщений: 5
|
Алгоритм Дейкстры в С
our task is to construct an undirected graph without loops based on the list of edges given in the input and then perform the following operations on this graph according to the input:
i - insert - inserting a new edge into the graph s - search - search for the shortest path in the graph according to the specified start and end u - update - modification of an existing edge in the graph (i.e. modification of the weight of the given edge), while the weight of the edge must not be changed to a negative number d - delete - remove an existing edge from the graph An edge is defined as a pair of two vertices, while the vertices are numbered with non-negative whole numbers from 0 to N, where N is the maximum number of vertices in the given graph. If the given operation fails, the error message " failed" is written in a separate line. The failure is, for example, when we try to add an edge that already exists, or when the search operation did not find any path for a given pair of vertices. The input of the program is the number N (max. number of vertices in the graph) followed by a space and the number M (number of edges in the initial graph) on the first line. There are M lines, where in each line there is one edge of the initial graph, in the format "(vertex_1, vertex2, weight)". This initial graph is followed by any number of lines, each line representing one command for one operation (ie, insert, search, update, or delete). The operation is expressed by the initial letter, i.e. i, s, u or d. The following are the data required for the given operation. The insert operation needs the following 3 data: vertex_1 number, vertex_2 number, edge weight (also an integer) The search operation needs the following 2 data: the number of the starting vertex, the number of the end (target) vertex The update operation needs the following 3 data: number of vertex_1, number of vertex_2, change of edge weight (also an integer) The delete operation needs the following 2 data: vertex_1 number, vertex_2 number The output is the shortest paths found by search operations, while the output format is as follows: : [vertex1, vertex2, vertex3, ..., last_vertex] In addition, the above-mentioned error messages are also output in case of operation failure, together with the edge above which the given operation failed. Do 22.04.2024, 09:00 Ukážkový vstup 10 30 (5, 0, 116) (5, 9, 163) (5, 2, 117) (5, 3, 110) (5, 7, 169) (5, 8, 188) (0, 8, 200) (0, 4, 113) (0, 1, 110) (0, 3, 129) (0, 6, 101) (8, 9, 160) (8, 1, 101) (8, 2, 146) (8, 4, 139) (1, 2, 159) (1, 7, 145) (1, 3, 182) (1, 9, 137) (2, 7, 184) (2, 9, 184) (2, 3, 176) (2, 6, 133) (2, 4, 199) (7, 6, 118) (7, 3, 172) (9, 4, 145) (9, 3, 180) (4, 3, 148) (3, 6, 129) s 3 8 s 5 3 s 3 0 s 4 6 d 4 3 i 4 7 90 s 6 9 s 9 5 s 2 1 s 5 2 u 2 7 56 s 1 2 s 6 9 s 9 3 u 5 0 52 d 1 7 i 1 5 85 d 7 3 d 3 6 i 8 3 47 i 0 7 78 s 4 3 s 5 4 u 8 3 -3 u 2 4 -26 d 5 0 u 5 7 -42 d 8 2 u 0 6 -57 d 0 8 u 2 6 91 d 5 8 u 0 6 42 u 8 1 -53 s 4 9 u 8 9 -39 s 1 4 s 0 5 u 7 4 -51 s 1 5 s 5 7 s 6 4 u 9 4 31 u 2 3 4 s 9 7 u 9 4 -96 i 6 4 82 i 2 8 75 d 0 1 d 1 9 i 6 8 1 i 6 5 78 i 1 6 53 s 2 7 i 7 8 34 s 9 5 s 8 9 u 8 4 -65 s 3 6 d 5 3 s 1 5 u 5 9 -25 u 8 6 -100 s 8 9 s 5 2 u 2 4 19 s 7 1 s 6 7 u 0 3 -28 s 3 1 s 0 3 s 7 6 s 8 2 u 5 9 -78 s 3 6 s 3 7 s 5 0 s 4 9 s 3 4 s 2 3 u 5 9 -37 s 9 6 s 6 7 u 9 3 -13 u 8 7 63 s 7 5 d 5 2 d 1 3 u 7 5 -89 s 6 0 d 5 9 s 0 5 s 0 9 d 5 1 d 8 4 s 8 0 s 6 8 d 7 6 u 9 3 -57 u 2 3 -49 d 0 4 s 3 2 u 8 3 -75 i 7 6 25 d 2 9 s 4 3 s 9 1 u 2 7 53 s 8 3 d 8 6 u 8 3 -2 s 5 3 s 7 5 i 5 2 44 d 1 2 s 5 7 u 0 3 42 u 5 6 56 u 2 6 17 s 9 6 Ukážkový výstup 283: [3, 1, 8] 110: [5, 3] 129: [3, 0] 214: [4, 0, 6] 309: [6, 3, 9] 163: [9, 5] 159: [2, 1] 117: [5, 2] 159: [1, 2] 309: [6, 3, 9] 180: [9, 3] 186: [4, 8, 3] 259: [5, 7, 4] 145: [4, 9] 187: [1, 8, 4] 195: [0, 1, 5] 85: [1, 5] 127: [5, 7] 157: [6, 7, 4] 215: [9, 4, 7] 194: [2, 8, 6, 7] 163: [9, 5] 121: [8, 9] 45: [3, 8, 6] 85: [1, 5] update 8 6 failed 121: [8, 9] 117: [5, 2] 82: [7, 8, 1] 35: [6, 8, 7] 92: [3, 8, 1] 101: [0, 3] 35: [7, 8, 6] 75: [8, 2] 45: [3, 8, 6] 78: [3, 8, 7] 164: [5, 6, 0] 80: [4, 9] 117: [3, 8, 7, 4] 119: [2, 8, 3] 101: [9, 5, 6] 35: [6, 8, 7] 127: [7, 5] 86: [6, 0] 116: [0, 7, 5] 193: [0, 4, 9] 87: [8, 6, 0] 1: [6, 8] 119: [3, 8, 2] update 8 3 failed 109: [4, 7, 6, 8, 3] 169: [9, 8, 1] 44: [8, 3] 177: [5, 7, 8, 3] 38: [7, 5] 38: [5, 7] 144: [9, 4, 7, 6] |
18.04.2024, 13:38 | #2 |
Регистрация: 06.04.2024
Сообщений: 5
|
Помогите с этим кодом, сверху написано задание, нужный ввод и нужный вывод, посоветовали добавить приоритетную очередь, но абсолютно никакая из моих версий не сработала
|
21.04.2024, 06:13 | #3 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,341
|
Лямзим код из статьи:
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм Дейкстры | Xopyc1996 | Помощь студентам | 0 | 05.05.2016 14:08 |
Алгоритм Дейкстры | Малайка | Общие вопросы Delphi | 0 | 05.03.2016 20:45 |
Алгоритм Дейкстры | Малайка | Общие вопросы Delphi | 3 | 13.02.2016 20:18 |
С. Алгоритм Дейкстры | XeniaZharinova | Помощь студентам | 0 | 26.12.2013 12:36 |
Алгоритм Дейкстры в xml | LENA_M | HTML и CSS | 0 | 29.05.2010 04:36 |