Probleme de informatică
Clasa a IX-a
Elementele de bază C++ (46)
Subprograme predefinite (1)
Fişiere text (2)
Algoritmi elementari (109)
Tablouri unidimensionale (83)
Tablouri bidimensionale (64)
Probleme diverse (13)
Clasa a X-a
Subprograme (funcții) (87)
Şiruri de caractere (49)
Tipul înregistrare (26)
Recursivitate (57)
Alocarea dinamică a memoriei (2)
Liste înlănţuite (25)
Algoritmul lui Lee (1)
Clasa a XI-a
Metoda "Divide et impera" (12)
Metoda Backtracking (85)
Metoda Greedy (6)
Programare dinamică (18)
Grafuri neorientate (37)
Grafuri orientate (38)
Arbori (33)
Clasa a XII-a
Elemente de bază C# (32)
POO în C# (13)
Programare vizuală în C# (11)
Examen de bacalaureat
Competențe digitale
Examen de atestat
Admitere UBB (18)
Harta unui oras este impartita in n intersectii si m strazi cu sens unic intre intersectii, fiecare strada avand o lungime. Pentru doua intersectii i si j poate exista atat strada de la i la j, cat si de la j la i.
Intr-o intersectie x se gaseste Julieta si intr-o intersectie y se gaseste Romeo. Cei doi se pot deplasa pe strazi in sensurile de parcurgere ale acestora.
Determinati intersectia in care trebuie sa se intalneasca cei doi astfel incat sa parcurga in total o distanta minima.
Pentru solutia obtinuta afisati intersectia, distanta parcursa de Julieta, distanta parcursa de Romeo si traseul parcurs de fiecate dintre ei.
Datele de intrare asigura ca cei doi se pot intalni.
Exemplu:
date.in
12 19 (n,m)
1 2 20 (intersectie 1, intersectie 2, lungime strada)
1 3 35
1 7 20
2 4 30
3 4 40
3 6 40
3 8 80
4 5 25
5 6 5
6 8 30
6 9 10
7 8 15
7 11 100
8 9 40
8 10 30
8 11 35
9 10 30
10 12 25
11 12 10
1 6 (Julieta, Romeo)
date.out
Intersectia: 8
Julieta merge: 35
Romeo merge: 30
Traseul Julietei: 1 7 8
Traseul lui Romeo: 6 8

#include<fstream>
using namespace std;
const int inf=100000;
int c[200][200],dr[200],dj[200],d[200],p[200],n,m,x,y,t[200], tj[200], tr[200];
ifstream f("d.in");
ofstream g("d.out");

void citire()
{ int i,j,k,cost;
  f>>n>>m;
  for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
      if(i==j) c[i][j]=0;
      else c[i][j]=inf;
  for(k=1;k<=m;k++)
    { f>>i>>j>>cost;
      c[i][j]=cost;
    }
  f>>x>>y;
}

void dijkstra(int s)
{ int i,j,k,minn;
  for(i=1;i<=n;i++)
     {
         d[i]=c[s][i];
         if(i!=s && d[i]!=inf) t[i]=s;
         else t[i]=0;
         p[i]=0;
     }

  p[s]=1;
  for(k=1;k<n;k++)
   { minn=inf;
     for(i=1;i<=n;i++)
       if(!p[i] && d[i]<minn)
                 { minn=d[i]; j=i;
			     }
     for(i=1;i<=n;i++)
       if(!p[i] && d[i]>d[j]+c[j][i])
            { d[i]=d[j]+c[j][i];
              t[i]=j;
            }
     p[j]=1;
   }
}

void drum(int i, int t[200])
{ if(t[i]) drum(t[i],t);
  g<<i<<" ";
}

int main()
 { int i,minn=100000,imin;
   citire();
   dijkstra(x);
   for(i=1;i<=n;i++) { dj[i]=d[i]; tj[i]=t[i]; }
   dijkstra(y);
   for(i=1;i<=n;i++) { dr[i]=d[i]; tr[i]=t[i]; }
   for(i=1;i<=n;i++)
      if(dj[i]+dr[i]<minn)
      {
          minn=dj[i]+dr[i];
          imin=i;
      }
   g<<"intersectia: "<<imin<<endl;
   g<<"Julieta merge: "<<dj[imin]<<endl;
   g<<"Romeo merge: "<<dr[imin]<<endl;
   g<<"Traseul Julietei: ";
   drum(imin,tj);
   g<<"\nTraseul lui Romeo: ";
   drum(imin,tr);
   f.close();
   g.close();
   return 0;
}

21 nov 2018
Site-ul conține 868 de probleme rezolvate
Copyright © 2009-2018 Muresan Vasile Ciprian