|
O’zbekiston respublikasi raqamli texnalogiyalar vazirligi
|
| bet | 3/4 | | Sana | 02.12.2023 | | Hajmi | 75,33 Kb. | | #109475 |
Bog'liq 2-AmaliyMasalaning quyilishi
Yo`nalish
Masalaning qo`yilishi: Katakchalari 0-9 (o`zlari ham kiradi) oraliqdagi raqamlar bilan tuldirilgan n ta satr va n ta ustundan iborat jadval berilgan. Jadvalning (1,1) katagidan (N,N) katagiga borishda bosib o`tilgan kataklardagi raqamlar yig`indisi minimal bo`lgan yo`l topilsin. Harakat faqat o`ngga va pastga yunalishlarda amalgam oshiriladi.
Chegaralanishlar: 2≤N≤250. Bajarilish vaqti 1 sekund.
Qiymat: “Youte.in”-qiymat fayli: -faylning birinchi satrida N soni joylashadi: keyingi N ta satrning har birida bo`sh joylarsiz N tadan raqamlar joylashadi.
Natija: “Youte.in” – natija fayli. N tadan belgisi bor. N ta satr faylga yoziladi. “#” yo`nalish shu katakdan o`tganligini bildiradi, “-” belgisi esa o`tmaganligini bildiradi. Agar minimal qiymatli yo`llar soni bir nechta bo`lsa ixtiyoriy bittasi olinadi.
Namunalar:
Qiymat
3
943
#include
#include
#include
using namespace std;
const int INF = INT_MAX; // Cheksizlik rejasini aniqlash
int findMinSumPath(int N, vector>& grid) {
vector> dist(N, vector(N, INF)); // Uzoqliklar massivi
// Boshlang'ich holatni sozlash
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (i == j) {
dist[i][j] = grid[i][j]; // Diagonal elementlar o'zlariga teng
}
}
}
// Floyd-Warshall algoritmi
for (int k = 0; k < N; ++k) {
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
|
| |
