Cod sursa(job #357724)

Utilizator katakunaCazacu Alexandru katakuna Data 20 octombrie 2009 16:24:14
Problema Drumuri minime Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
//Dijkstra O (N * M)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

#define Nmax 1510
#define Mmax 2510
#define INF 1 << 30
#define MOD 104659

int a, b, n, m, i, j, nod, fiu;
int viz[Nmax], Nr[Nmax];
double Cst, cst[Nmax], c, Min;
vector < pair <int, double> > V[Nmax];

int egal (double a, double b) {
	if ( a - b >= -0.0000000001 && a - b <= 0.0000000001 ) return 1;
	return 0;
}

int main () {

	FILE *f = fopen ("dmin.in", "r");
	FILE *g = fopen ("dmin.out", "w");

	fscanf (f, "%d %d", &n, &m);
	for (i = 1; i <= m; i++) {
		fscanf (f, "%d %d %lf", &a, &b, &c);
		c = log(c);
		V[a].push_back (make_pair (b, c));
		V[b].push_back (make_pair (a, c));
	}
	
	for (i = 2; i <= n; i++)
		cst[i] = INF; 
	
	cst[1] = 0; Nr[1] = 1;
	for (i = 1; i <= n; i++) {
		Min = INF;
		for (j = 1; j <= n; j++) {
			if (Min > cst[j] && !viz[j]) {
				Min = cst[j];
				nod = j;
			}
		}
		
		viz[nod] = 1;
		for (j = 0; j < (int)V[nod].size(); j++) {
			fiu = V[nod][j].first;
			Cst = V[nod][j].second + cst[nod]; 
			if ( egal (cst[fiu], Cst) ) {
				Nr[fiu]+= Nr[nod];
				if (Nr[fiu] > MOD) Nr[fiu]-= MOD;
			}
			
			if ( cst[fiu] > Cst ) {
				cst[fiu] = Cst;
				Nr[fiu] = Nr[nod];
				if (Nr[fiu] > MOD) Nr[fiu]-= MOD;
			}
		}
	}
	
	for (i = 2; i <= n; i++)
		fprintf (g, "%d ", Nr[i]);
	
	fclose (f);
	fclose (g);
	
	return 0;

}