Cod sursa(job #307850)

Utilizator Mishu91Andrei Misarca Mishu91 Data 25 aprilie 2009 12:33:40
Problema Drumuri minime Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>

using namespace std;

#define MAX_N 1505
#define INF 0x3f3f3f3f
#define MOD 104659
#define eps 1e-9

#define x first
#define d second

#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)  

int N, M;
vector <pair <int, double> > G[MAX_N];
double D[MAX_N];
int T[MAX_N];

void citire()
{
	scanf("%d %d",&N, &M);
	
	while(M--)
	{
		int x, y;
		double d;
		
		scanf("%d %d %lf",&x, &y, &d);
		double p = log(d);
		
		G[x].push_back(make_pair(y, p));
		G[y].push_back(make_pair(x, p));
	}
}

void solve()
{
	queue <int> Q;
	bitset <MAX_N> viz;
	
	for(int i = 1; i < MAX_N; ++i)
		D[i] = INF;
	
	D[1] = 0;
	T[1] = 1;
	Q.push(1);
	viz[1] = 1;
	
	for(;!Q.empty(); Q.pop())
	{
		int nod = Q.front();
		viz[nod] = 0;
		
		foreach(G[nod])
		{
			int act = it -> x;
			double dact = it -> d;
			
			if(fabs(D[nod] + dact - D[act]) < eps)
			{
				T[act] += T[nod];
				if(T[act] > MOD)
					T[act] -= MOD;
			}
			
			if(D[act] - D[nod] - dact > eps)
			{
				D[act] = D[nod] + dact;
				T[act] = T[nod];
				if(!viz[act])
				{
					Q.push(act);
					viz[act] = 1;
				}
			}
			

		}
	}
		
	for(int i = 2; i <= N; ++i)
		printf("%d ",T[i]);
}

int main()
{
	freopen("dmin.in","rt",stdin);
	freopen("dmin.out","wt",stdout);
	
	citire();
	solve();
}