| ENG RUS | Timus Online Judge |
Обсуждение задачи 1004. ЭкскурсияLe Phuoc Hai Son A good algorithm [8] // Задача 1004. Экскурсия 11 июн 2001 15:03 Any one here know a good algorithm to find the shortest loop in a graph? Dinh Quang Hiep (mg9h@yahoo.com) Re: A good algorithm [3] // Задача 1004. Экскурсия 11 июн 2001 23:12 kheo thi N^3, con khong thi khoang N^4 ! Tong Hop Vo Dich @ QH@ Stefan Pochmann ENGLISH, please. (Was: A good algorithm) [1] // Задача 1004. Экскурсия 12 июн 2001 05:18 Don't you understand, what "Write in English, please." means? Even if you knew him personally, it would be more friendly to the rest of us if you followed this advice. It's kind of annoying not to understand people talk. Best regards, Stefan Pochmann Dinh Quang Hiep (mg9h@yahoo.com) Re: ENGLISH, please. (Was: A good algorithm) <= sometime i wanna use my mother languague, ok ;) ? // Задача 1004. Экскурсия 12 июн 2001 19:31 > Don't you understand, what "Write in English, please." > means? Even if you knew him personally, it would be > more friendly to the rest of us if you followed this > advice. It's kind of annoying not to understand people > talk. > > Best regards, > Stefan Pochmann Le Phuoc Hai Son Re: A good algorithm // Задача 1004. Экскурсия 12 июн 2001 11:24 u CO THE NOI RO VE THUAT TOAN O. TUI CHI NGHI RA 2 CACH: -DUNG LOANG CHI TUNG CAP DINH -DUNG LOANG DE TIM CHU TRINH tUI KHONG BIET CACH THU 2 CO DUNG O? HNT Re: A good algorithm [3] // Задача 1004. Экскурсия 12 июн 2001 08:37 Mmmm, I think that you shouldn't know it ( N^3 Dynamic Programming) > Any one here know a good algorithm to find the shortest > loop in a graph? Le Phuoc Hai Son Re: A good algorithm [2] // Задача 1004. Экскурсия 12 июн 2001 11:27 wHY DON'T YOU EXPLAIN THAT ALGORITHM. iN VIETNAMESE IT'S "QUY HOACH DONG"??? Dinh Quang Hiep (mg9h@yahoo.com) Re: A good algorithm <= this one, is not "KHEO" (O(N^4)) [1] // Задача 1004. Экскурсия 12 июн 2001 20:18 choose one node for the first city i, the "remove" it from the list, now, you find the shortest path between each pairs of the remaining nodes, (using floyd algorithm with O(N^3)) for each d(u, v) (u <> v), compare the sum A[i][u] + d[u][v] + A[v][i] with the best root There's some tricky that, with each route, you can "convert" it the another route, which is better for programming, satisfy that the first city is the lowest number => when try to find the shortest way like the algorithm above, u and v always > i ! Good luck ! QH@ Pete Lupherenko Re: A good algorithm <= this one, is not // Задача 1004. Экскурсия 21 окт 2001 15:08 > choose one node for the first city i, the "remove" it from > the list, now, you find the shortest path between each pairs > of the remaining nodes, (using floyd algorithm with O (N^3)) > for each d(u, v) (u <> v), compare the sum A[i][u] + d[u] [v] > + A[v][i] with the best root > > There's some tricky that, with each route, you can "convert" > it the another route, which is better for programming, > satisfy that the first city is the lowest number => when try > to find the shortest way like the algorithm above, u and v > always > i ! > > Good luck ! > > QH@ But why O (N^3) ???? Floyd's algorithm ( O(N^3) ) will be used several ( O(N) ) times! |