Cod sursa(job #1360640)

Utilizator starduststardust stardust Data 25 februarie 2015 16:59:35
Problema Algoritmul lui Dijkstra Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#define inf 1<<30
#define maxn 500010

using namespace std;

int n, m;
vector<pair<int, int> >	a[maxn];
priority_queue< pair<int, int> > pq;
int d[maxn];

void djikstra()
{
	for (int i = 2; i <= n; i++)
		d[i] = inf;

	d[1] = 0;

	pq.push(make_pair(1, 0));
	while (pq.size() > 0)
	{
		int nod = pq.top().first;
		pq.pop();
		for (int i = 0; i < a[nod].size(); i++)
		{
			int nodc = a[nod][i].first;
			int costc = a[nod][i].second;
			if (d[nodc] > d[nod] + costc)
			{
				d[nodc] = d[nod] + costc;
				pq.push(make_pair(nodc,d[nodc]));
			}
		}
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d", &n, &m);
	int x, y, z;
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		a[x].push_back(make_pair(y, z));
	}
	djikstra();
	for (int i = 2; i <= n; i++)
	{
		printf("%d ", d[i]);
	}
}