Cod sursa(job #2427292)

Utilizator qusyNastase Alexandru qusy Data 31 mai 2019 15:32:26
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#if 0
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>


using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <int> vec[50005];
vector <int> vec_cost[50005];
priority_queue<pair<int, int>> myheap;
int dist[50005];
int viz[50005];

#define max_size 20000005


int main()
{
	int N, M, x, y, c, i, k, index;
	fin >> N >> M;
	for (i = 1; i <= M; i++)
	{
		fin >> x >> y >> c;
		vec[x].push_back(y);
		vec_cost[x].push_back(c);
	}

	for (i = 1; i <= N; i++) {
		if (i == 1) dist[i] = 0;
		else
			dist[i] = max_size;
		myheap.push(make_pair(-dist[i], i));
	}
	while (!myheap.empty())
	{
		pair<int, int>p = myheap.top();
		index = p.second;
		myheap.pop();
		if (viz[index] == 1);
		else
		{
			viz[index] = 1;

			int lim = vec[index].size();
			for (k = 0; k < lim; k++)
			{
				int vecin = vec[index][k];
				if (dist[vecin] > (dist[index] + vec_cost[index][k]))
				{
					dist[vecin] = dist[index] + vec_cost[index][k];
					myheap.push(make_pair(-dist[vecin], vecin));
				}
			}

		}
	}
	for (i = 2; i <= N; i++) {
		if (dist[i] == max_size)
			dist[i] = 0;
		fout << dist[i] << " ";
	}
	return 0;
}
#endif