Fan nomi: Algoritmlarni Loyihalash Fakultet

Muhammad al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti Urganch filiali

9-AMALIY ISH

Fan nomi: Algoritmlarni Loyihalash
Fakultet: Telekomunikatsiya Texnologiyalari Guruh: 941-21
Bajardi: Ruzmetov Muzaffar
Tekshirdi: Yusupova Janar
ICMP 132 masala o`zbekcha sharti va yechimi

Berilgan yo'naltilgan to'g'ri bobli bo'lgan graf uchun S va F tug'unlar orasidagi eng qisqa masofani topishingiz kerak.

Kirish ma'lumotlari Kirish faylida INPUT.TXT da uchta raqam yozilgan: N, S va F (1 ≤ N ≤ 100; 1 ≤ S, F ≤ N), bu yerda N - grafning tug'unlar sonini ifodalaydi. Keyingi N qator bo'yicha N ta raqam yozilgan - grafning qaralar matrisi, bu yerda i-qator j-ustunidagi raqam i dan j ga yo'l tashlagan qiyinchilikni ifodalaydi: -1 - uchunlar orasida yo'l yo'q, va 0 dan 100 gacha bo'lgan istalgan musbat butun son - ushbu og'irligi bo'lgan yo'l mavjudligini anglatadi. Matrisning asosiy diagonalida doimiy ravishda nol yozilgan.
Chiqish ma'lumotlari OUTPUT.TXT faylida topilgan masofa yoki -1 (agar berilgan tug'unlar orasida yo'l mavjud bo'lmasa) chiqarilishi lozim.

#include

#include
#include

using namespace std;

const int INF = 1e9;

int main() {

int N, S, F;
cin >> N >> S >> F;

vector> graph(N, vector(N));

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> graph[i][j];
}
}

vector distance(N, INF);

distance[S - 1] = 0;

queue q;

q.push(S - 1);

while (!q.empty()) {

int current = q.front();
q.pop();

for (int i = 0; i < N; i++) {

if (graph[current][i] != -1 && distance[current] + graph[current][i] < distance[i]) {
distance[i] = distance[current] + graph[current][i];
q.push(i);
}
}
}

if (distance[F - 1] == INF) {

cout << -1 << endl;
} else {
cout << distance[F - 1] << endl;
}

return 0;

}