Cod sursa(job #2741375)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 15 aprilie 2021 22:12:15
Problema Algoritmul lui Dijkstra Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define NMAX 50009
#define INF 99999999999999LL
#define int long long int
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m;
vector< pair<int, int> >g[NMAX];
void citire();
void djk();
bool uz[NMAX];
int sol[NMAX];
class compar
{
public:
	bool operator ()(pair<int, int>a, pair<int, int> b)
	{
		return a.second > b.second || a.second == b.second && a.first > b.first;
	}
};
priority_queue <pair<int, int>, vector<pair<int, int> >, compar> H;
int32_t main()
{
	citire();
	djk();

	return 0;
}void citire()
{
	int i, j;
	int x, y, cost;
	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> y>>cost;
		g[x].push_back({ y,cost });

	}

}
void djk()
{
	int i;
	for (i = 0; i < NMAX; i++)
		sol[i] = INF;
	sol[1] = 0;
	H.push({ 1,0 });
	uz[1] = 1;
	while (!H.empty())
	{
		pair<int, int>act = H.top(); H.pop();
		uz[act.first] = 0;

		for (i = 0; i < g[act.first].size(); i++)
		{
			int vec = g[act.first][i].first;
			int cost = g[act.first][i].second;
			if (sol[vec] > act.second + cost)
			{
				sol[vec] = sol[ act.first] + cost;
				if (!uz[vec])
				{
					uz[vec] = 1;
					H.push({ vec,sol[vec] });
				}
			}
		}
	}
	for (i = 2; i <= n; i++)
		if (sol[i] == INF)
			fout << 0 << " ";
		else
			fout << sol[i] << " ";

}