Cod sursa(job #1757154)

Utilizator irinapatularuPatularu Irina irinapatularu Data 14 septembrie 2016 17:01:44
Problema Algoritmul lui Dijkstra Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <list>
#include <queue>

#define NMAX 50002
#define INF 1234566000

using namespace std;

bool operator <(const pair<int, int>& a, const pair<int, int>& b){
	return a.second < b.second;
}

int N, M;
vector<list<pair<int, int> > > adList(NMAX);
priority_queue<pair<int, int> > PQ;
int distances[NMAX], visited[NMAX];

void solve(){

	PQ.push(make_pair(1, 0));

	while(!PQ.empty()){
		pair<int, int> node = PQ.top();
		PQ.pop();
		visited[node.first] = 0;

		list<pair<int, int> > :: iterator it = adList[node.first].begin();
		while(it != adList[node.first].end()){
			pair<int, int> neigh = *it;
			if(distances[neigh.first] > distances[node.first] + neigh.second){
				distances[neigh.first] = distances[node.first] + neigh.second;
				if(visited[neigh.first] == 0){
					PQ.push(make_pair(neigh.first, distances[neigh.first]));
					visited[neigh.first] = 1;
				}
			}
			it++;
		}
	}

}

int main(){
	int a, b, c;
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");

	f >> N >> M;
	for(int i = 0; i < M; i++){
		f >> a >> b >> c;
		adList[a].push_back(make_pair(b, c));
	}
	f.close();

	for(int i = 1; i <= N; i++)
		distances[i] = INF;
	distances[1] = 0;
	visited[1] = 1;

	solve();

	for(int i = 2; i <= N; i++){
		if(distances[i] == INF)
			g << "0 ";
		else
			g << distances[i] << " ";
	}

	g.close();
	return 0;

}