Cod sursa(job #2448374)

Utilizator red_devil99Mancunian Red red_devil99 Data 16 august 2019 19:22:08
Problema Algoritmul lui Dijkstra Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include<bits/stdc++.h>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define maxn 50005
#define INF 1 << 30
int N, M;
int x, y, val;
std::vector<pair<int, int>> v[maxn];
int cost[maxn];
int verif[maxn];

struct comp{

	    bool operator()(int x,int y){
	
            return cost[x]>cost[y];
	
    }

};
void dij(int nod){
	for(int i = 1; i <= N; i++){
		cost[i] = INF;
	}
	cost[nod] = 0;
	verif[nod] = 1;
	priority_queue <int, vector<int>, std::greater<int>> q;
	q.push(nod);
	while(!q.empty()){
		int a = q.top();
		verif[a]=0;
		q.pop();
		for(int i = 0; i < v[a].size(); i++){
			int b = v[a][i].first;
			int c = v[a][i].second;
			if(cost[b]>cost[a]+c){
				cost[b]=cost[a]+c;

			}
			if(verif[b]==0){
				verif[b]=1;
				q.push(b);
			}
		}

	}
}

int main(){
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin >> N >> M;
	for(int i = 1; i <= M; i++){
		fin >> x >> y >> val;
		v[x].push_back(make_pair(y, val));
	}
	
	dij(1);
	for(int i = 2; i <= N; i++){
		if(cost[i]==INF){
			fout <<"0 ";
		}else{
			fout << cost[i]<<" ";
		}
	}
	return 0;
}