Pagini recente » Cod sursa (job #437975) | Cod sursa (job #1289228) | Cod sursa (job #781710) | Cod sursa (job #468819) | Cod sursa (job #2590593)
#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>
#include <utility>
#define INFINIT 100000000
#define MAX 100000
using namespace std;
typedef pair<int,int> PAIR;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int nrNoduri, nrMuchii, distanta[MAX];
bool vizitat[MAX];
vector <PAIR> reprezentareGraf[MAX];
void Dijkstra(int NodStart){
for(int i = 1 ; i <= nrNoduri; i ++ ){ //initializare vectori
vizitat[i] = false; //marcam toate nodurile ca fiind nevizitate
distanta[i] = INFINIT;
}
int lim = reprezentareGraf[NodStart - 1].size();
for (int i = 0; i < lim; i++ ) //distanta initiala de la NodStart la celelalte
distanta[reprezentareGraf[NodStart - 1][i].first] = reprezentareGraf[NodStart - 1][i].second;
vizitat[NodStart] = true;
distanta[NodStart] = 0; //costul de la nodul sursa la nodul sursa va fi implicit 0
for(int j = 0; j < nrNoduri - 1; j++){ //nrNoduri - 1 pt ca nodul sursa iese din calcul
int minim = INFINIT; //vom salva costul minim de la nodul sursa la fiecare nod in parte
int NodCurent = -1;
for(int vecin = 1; vecin <= nrNoduri; vecin++){ //aflu costul minim de la nodul sursa la nodul i
if( !vizitat[vecin] && distanta[vecin] < minim ){
minim = distanta[vecin];
NodCurent = vecin; //salvam nodul cu costul minim
}
}
vizitat[NodCurent] = true;
lim = reprezentareGraf[NodCurent - 1].size();
for(int i = 0; i < lim; i++){ //parcurg vecinii nodului curent ( cel cu cost minim gasit anterior )
int vecin = reprezentareGraf[NodCurent - 1][i].first;
if( !vizitat[vecin] && distanta[vecin] > distanta[NodCurent] + reprezentareGraf[NodCurent - 1][i].second )
distanta[vecin] = distanta[NodCurent] +reprezentareGraf[NodCurent - 1][i].second;
}
}
for (int i = 2; i <= nrNoduri; i++)
if ( distanta[i] == INFINIT )
fout<< 0 <<" ";
else
fout<<distanta[i]<<" ";
}
int main(){
fin >> nrNoduri >> nrMuchii;
for (int i = 1; i <= nrMuchii; i++) {
int x , y , cost;
fin >> x >> y >> cost;
reprezentareGraf[x-1].push_back(make_pair(y,cost));
}
Dijkstra(1);
return 0;
}