Cod sursa(job #88364)

Utilizator blasterzMircea Dima blasterz Data 1 octombrie 2007 20:35:29
Problema Drumuri minime Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
using namespace std;
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#define maxn 1501
#define pb push_back
#define eps 0.00000000001
#define mod 104659
struct nod { int n; double c;nod(){};nod(int a, double b){n=a; c=b;};};

vector<nod>a[maxn];
int n, m;

double d[maxn];
int dp[maxn];

struct cmp{
  bool operator()(const double &a,const double &b)const
  {
    if(a-b>eps)return 1;
    return 0;

  }
};

void read()
{
  freopen("dmin.in","r",stdin);
  scanf("%d %d\n", &n, &m);
  int p, q, c;
  for(int i=1;i<=m;++i)
    {
      scanf("%d %d %d\n", &p, &q, &c);
      a[p].pb(nod(q, log(c)));
      a[q].pb(nod(p, log(c)));
     
    }
}

void dijkstra()
{
  priority_queue<int, vector<int>, cmp> Q;
  
  for(int i=1;i<=n;++i) d[i]=0x3f3f3f3f;
  d[1]=0;
  Q.push(1);
  vector<nod>::iterator it;
  int u;
  

  while(!Q.empty())
    {
      u=Q.top();
      Q.pop();
      for(it=a[u].begin();it!=a[u].end();++it)
	if(d[it->n] - (d[u]+it->c) >eps)
	  {
	    d[it->n]=d[u]+it->c;
	    Q.push(it->n);
	  }
      
    }
  

}

void dynamic()
{
  priority_queue<int, vector<int>, cmp> Q;
  
  // for(int i=1;i<=n;++i) d[i]=0x3f3f3f3f;
  //d[1]=0;
  Q.push(1);
  vector<nod>::iterator it;
  int u;
  bool use[maxn];
  memset(use, 0, sizeof(use));
  //use[1]=1;
  dp[1]=1;
  while(!Q.empty())
    {
      u=Q.top();
      Q.pop();
       if(use[u])continue;
      use[u]=1;
      
      for(it=a[u].begin();it!=a[u].end();++it)
		if(!use[it->n])
	if(d[it->n] - (d[u]+it->c) <=eps)
	  {
	    // d[it->n]=d[u]+it->c;
	    //  printf("da\n");
	    dp[it->n]+=dp[u];
	    dp[it->n]%=mod;
	    
	    Q.push(it->n);
	  }
      
    }
}




int main()
{
  read();
  dijkstra();
  dynamic();
  freopen("dmin.out","w",stdout);
  for(int i=2;i<=n;++i)printf("%d ", dp[i]);
  printf("\n");

  return 0;
}