Cod sursa(job #1500110)

Utilizator ion824Ion Ureche ion824 Data 11 octombrie 2015 15:38:47
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <queue>
#include <vector>
#include <algorithm>
#include <fstream>
#include <functional>

using namespace std;
const int NMAX = 50003;
const int INF = 0x3f3f3f3f;

int N, M;

int d[NMAX];

typedef pair<int, int> ii;
vector<ii> g[NMAX];

void Dijkstra(int nod)
{
	fill(d, d + N + 1, INF);

	priority_queue<ii, vector<ii>, greater<ii> > Q;

	d[nod] = 0;
	Q.push(ii(0, nod));

	while (!Q.empty())
	{
		ii it = Q.top();
		Q.pop();

		int dist = it.first;
		nod = it.second;

		if (dist <= d[nod])
		{
			for (auto &x : g[nod])
			if (d[nod] + x.second < d[x.first])
			{
				d[x.first] = d[nod] + x.second;
				Q.push(ii(d[x.first], x.first));
			}
		}
	}
}

int main(){
	ifstream cin("dijkstra.in");
	ofstream cout("dijksra.out");

	cin >> N >> M;

	int x, y, c;
	for (int i = 0; i < M; ++i)
	{
		cin >> x >> y >> c;
		g[x].push_back(ii(y, c));
		g[y].push_back(ii(x, c));
	}

	Dijkstra(1);

	for (int i = 2; i <= N; ++i)
		cout << d[i] << '\n';

	cout.close();

	return 0;
}