Cod sursa(job #2403312)

Utilizator Vali_DeaconuVali Deaconu Vali_Deaconu Data 11 aprilie 2019 14:04:44
Problema Algoritmul lui Dijkstra Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

#define __DIRECTED_GRAPH

using namespace std;

class Graph {
	private: 
		unsigned int V;
		vector< pair<int, int> > *L;

	public:
		Graph(unsigned int V);
		~Graph();
		void addEdge(unsigned int u, unsigned int v, unsigned int cost);
		vector<int> dijkstra(unsigned int start);
};

Graph::Graph(unsigned int V) {
	this->V = V;

	this->L = new vector< pair<int, int> >[V];
}

Graph::~Graph() {
	for (unsigned int i = 0; i < V; ++i) {
		L[i].clear();
	}
	//delete L;
}

void Graph::addEdge(unsigned int u, unsigned int v, unsigned int cost) {
	L[u].push_back(make_pair(v, cost));
	#ifndef __DIRECTED_GRAPH
	L[v].push_back(make_pair(u, cost));
	#endif
}

vector<int> Graph::dijkstra(unsigned int start) {
	priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;

	const unsigned int INF = numeric_limits<int>::max();
	vector<int> dist(V, INF);

	pq.push(make_pair(0, start));
	dist[start] = 0;
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();

		for (unsigned int i = 0; i < L[u].size(); ++i) {
			int v = L[u][i].first;
			int cost = L[u][i].second;

			if (dist[v] > dist[u] + cost) {
				dist[v] = dist[u] + cost;
				pq.push(make_pair(dist[v], v));
			}
		}
	}
	for (unsigned int i = 0; i < dist.size(); ++i) {
		if (dist[i] == INF)
			dist[i] = 0;
	}

	return dist;
}

int main() {
	ifstream fin("dijkstra.in");
	
	unsigned int V, E;
	fin >> V >> E;
	
	Graph * G = new Graph(V);

	unsigned int u, v, w;
	for (unsigned int i = 0; i < E; ++i) {
		fin >> u >> v >> w;
		G->addEdge(u - 1, v - 1, w);
	}

	fin.close();

	vector<int> dist = G->dijkstra(0);

	ofstream fout("dijkstra.out");
	for (unsigned int i = 1; i < V; ++i) {
		fout << dist[i] << " ";
	}
	fout.close();

	delete G;

	return 0;
}