Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <conio.h>
- #include <stdlib.h>
- #include <iostream>
- using namespace std;
- int a[20][20];
- int vizitat[20];
- void Afisare() {
- for (int i = 0;i < 20;i++) {
- for (int j = 0;j < 20;j++) {
- cout << a[i][j] << " ";
- }
- cout << endl;
- }
- }
- void main() {
- char *nume[20] = { "Arad","Bucuresti","Craiova", "Drobeta","Eforie","Fagarasi","Giurgiu","Hirsova","Iasi","Lugoj","Mehadia","Neamt","Oradea","Pitesti","Rimnicu Valcea","Sibiu","Timisoara","Urziceni","Vaslui","Zerind" };
- // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
- int noduri[20];
- int nr_noduri = 0;
- int n = 20;
- int oras_Start = 12, oras_Destinatie = 6;
- int adancime[20]; //stocheaza adancimea fiecarui nod //
- int limita = 15;
- int solutie[20];
- int parinte[20];
- int nr_solutie = 0;
- int cost[20];
- /*
- cout << "Introduceti oras start: \n";
- cin >> oras_Start;
- cout << "Introduceti oras destinatie: \n";
- cin >> oras_Destinatie;
- */
- const int o_Destinatie = oras_Destinatie;
- a[0][16] = 118;
- a[0][15] = 140;
- a[0][19] = 75;
- a[1][5] = 211;
- a[1][6] = 90;
- a[1][13] = 101;
- a[1][17] = 85;
- a[2][3] = 120;
- a[2][13] = 138;
- a[2][14] = 146;
- a[3][10] = 75;
- a[4][7] = 86;
- a[5][15] = 99;
- a[7][17] = 98;
- a[8][11] = 87;
- a[8][18] = 92;
- a[9][10] = 70;
- a[9][16] = 111;
- a[12][19] = 71;
- a[12][15] = 151;
- a[13][14] = 97;
- a[14][15] = 80;
- a[17][18] = 142;
- /*a[0][16] = 1;
- a[0][15] = 1;
- a[0][19] = 1;
- a[1][5] = 1;
- a[1][6] = 1;
- a[1][13] = 1;
- a[1][17] = 1;
- a[2][3] = 1;
- a[2][13] = 1;
- a[2][14] = 1;
- a[3][10] = 1;
- a[3][2] = 1;
- a[4][7] = 1;
- a[5][1] = 1;
- a[5][15] = 1;
- a[7][17] = 1;
- a[8][11] = 1;
- a[8][18] = 1;
- a[9][10] = 1;
- a[9][16] = 1;
- a[12][19] = 1;
- a[12][15] = 1;
- a[13][14] = 1;
- a[14][15] = 1;
- a[17][18] = 1;*/
- for (int i = 0;i < 20;i++) {
- for (int j = 0;j < 20;j++) {
- a[j][i] = a[i][j];
- }
- }
- //cout << "Afisare" << endl;
- // Afisare();
- // int cautare;
- // cout << "Introduceti indicele orasului caruia vreti sa ii aflam vecinii: "; cin >> cautare;cout << endl;
- // cout << nume[cautare] << " are vecinii:" << endl;
- // for (int i = 0;i < 20;i++)
- // if (a[cautare][i] == 1) {
- // cout << nume[i] << " ";
- // }
- // CAUTAREA CU COST UNIFORM
- noduri[0] = oras_Start;
- nr_noduri++;
- vizitat[oras_Start] = 1;
- cost[oras_Start] = 0;
- int gasit = 0;
- int nod;//nodul curent pe care il initializam
- while (gasit == 0 && (nr_noduri != 0)) {
- nod = noduri[0];//scoatem primul element din lista de noduri si il retinem in noduri
- for (int i = 0;i < nr_noduri - 1;i++) {
- noduri[i] = noduri[i + 1];
- }
- nr_noduri--;
- if (nod == oras_Destinatie) {
- gasit = 1;
- }
- else {
- for (int i = 0;i < 20;i++) {
- if (a[nod][i]!=0 &&((vizitat[i]==0)||((vizitat[i]==1)&&(cost[i]>cost[nod] + a[nod][i])))){//orasele conectate de nod && nevizitate
- // costul vechi e mai mare decat noul cost
- // orasele conectate de nod SI (fie sunt nevizitate , fie au fost vizitate) dar la o adancime mai mare decat adancimea PE care ar primi-o acum
- //e prea mare programul sa-ti dai seama cv =.=" /
- cost[i] = cost[nod] + a[nod][i];
- int j = 0;
- while (cost[i] > cost[noduri[j]] && j < nr_noduri) {
- j++;// j va fi pozitia PE care inserez in lista de noduri
- }
- for (int i = nr_noduri;i > j;i--) { // Adaug acel i astfel incat lista sa fie ordonata crescator dupa cost
- noduri[i] = noduri[i - 1]; // noduri[i-1] si asta in loc de a mai pune i-- la for
- }
- noduri[j] = i; // aceste 3 linii se modifica la cautarea in latime
- nr_noduri++;
- vizitat[i] = 1;
- parinte[i] = nod;
- adancime[i] = adancime[nod] + 1;
- }
- }
- }
- }
- if (gasit == 0) {
- cout << "\nNu s-a gasit\n\n";
- }
- else {
- while (oras_Destinatie != oras_Start) {
- solutie[nr_solutie++] = oras_Destinatie;
- oras_Destinatie = parinte[oras_Destinatie];
- }
- solutie[nr_solutie] = oras_Start;
- cout << "\nCel mai rapid drum dintre " << nume[oras_Start] << " si " << nume[o_Destinatie] << " este\n";
- for (int i = nr_solutie;i >= 0;i--) {
- cout << nume[solutie[i]] << " ";
- }
- }
- _getch();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement