Cod sursa(job #713170)

Utilizator hunter_ionutzzzFarcas Ionut hunter_ionutzzz Data 14 martie 2012 12:13:31
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.12 kb
#include<fstream>
#include<vector>
#define lung 36001
#define inf 1 << 30
using namespace std;
ifstream fin("catun.in");
ofstream fout("catun.out");
struct nod{int val,cost;
		   nod *next;
};
nod *v[36001],*q;
int n,m,a,i,poz[lung],h[lung],d[lung],fort[lung],rasp[lung],k,nr;
bool viz[lung];
inline void downheap (int x)
{int fiu;
	while (x <= k)
	{   fiu = x;
	    if ((x << 1) <= k)
		{   fiu = x << 1;
		    if (fiu+1 <=k && d[h[fiu+1]] < d[h[fiu]])
				++fiu;
		}
		else
			break;
		if (d[h[fiu]] < d[h[x]])
		{   poz[h[fiu]] = x;
		    poz[h[x]] = fiu;
			h[x] = h[x] + h[fiu] - (h[fiu] = h[x]);
			x = fiu;
		}
		else
			break;
	}
}
inline void upheap (int x)
{int tata;
	while (x > 1)
	{   tata = x >> 1;
	    if (d[h[x]] < d[h[tata]])
		{   poz[h[x]] = tata;
			poz[h[tata]] = x;
			h[x] = h[x] + h[tata] - (h[tata] = h[x]);
			x = tata;
		}
		else
			x = 1;
	}
}
inline void dijkstra(int aux)
{int minim,i;
	for (i=1;i<=n;++i)
	{   d[i] = inf;
	    poz[i] = -1;
	}
	k=0;
	poz[aux] = 1;
	h[1] = aux;
	d[aux] = 0;
	++k;
	while (k)
	{   if (viz[h[1]])
		{   rasp[a] = h[1];
	        int ind = d[h[1]];
	        while (k)
			{   if (viz[h[k]])
					if (ind == d[h[k]] && h[k] < rasp[a])
						rasp[a] = h[k];
				--k;
	        }
        	break;
		}
		minim = h[1];
	    h[1] = h[1] + h[k] - (h[k] = h[1]);
		poz[h[1]] = 1;
		--k;
		downheap(1);
		q = v[minim];
		while (q)
		{   if (d[q->val] > d[minim] + q->cost)
			{	d[q->val] = d[minim] + q->cost;
				if (poz[q->val] != -1)
					upheap(poz[q->val]);
			    else
				{   h[++k] = q->val; 
					poz[h[k]] = k;
					upheap(k);
				}
			}
			q = q -> next;
		}
	}
}
int main()
{int b,c;
    fin >> n >> m >> nr;
	for (i=1;i<=nr;++i)
	{	fin >> a;
	    viz[a] = true;
    } 
    for (i=1;i<=m;++i)
	{	fin >> a >> b >> c;
	    q = new nod;
	    q -> val = b;
		q -> cost = c;
		q -> next = v[a];
		v[a] = q;
		q = new nod;
		q -> val = a;
		q -> next = v[b];
		q -> cost = c;
		v[b] = q;
	}
	for (a=1;a<=n;++a)
		if (!viz[a])
			dijkstra(a);
	for (a=1;a<=n;++a)
		fout << rasp[a] << " ";
	return 0;
}