# Cod sursa(job #43428)

Utilizator Data 30 martie 2007 08:18:10 Drumuri minime 5 cpp done Arhiva de probleme 1.06 kb
``````#include <fstream.h>
#define inf 10000
ifstream f("dmin.in");
ofstream g("dmin.out");
long t=0,n;
void dr(long vf1,long vf2,long co,long cost,long (*c)[100])
{
long i;
if (vf1==vf2&&co==cost) {t++;return;}
else
for (i=1;i<=n;i++)
if (c[vf1][i]!=inf&&i!=vf1)
dr(i,vf2,co*c[vf1][i],cost,c);
}

int main()
{
long *cost,(*c)[100],*v,x,y,min,poz,co,m,i,j,ii,ij;
f>>n>>m;
v=new long[n+1];
cost=new long[n+1];
c=new long[100][100];
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (i!=j) c[i][j]=inf;
else c[i][j]=0;
for (i=1;i<=m;i++)
{
f>>x>>y>>co;
c[x][y]=co;
}
x=1;
for (ii=2;ii<=n;ii++)
{
t=0;
for (ij=1;ij<=n;ij++) v[ij]=cost[ij]=0;
y=ii;
v[1]=1;
for (i=1;i<=n;i++)
cost[i]=c[x][i];
for (i=1;i<n;i++)
{
min=inf;
for (j=1;j<=n;j++)
if (!v[j]&&cost[j]<min)
{
min=cost[j];
poz=j;
}
v[poz]=1;
for (j=1;j<=n;j++)
if (!v[j]&&cost[j]>cost[poz]*c[poz][j])
cost[j]=cost[poz]*c[poz][j];
}
dr(x,y,1,cost[y],c);
g<<t%104659<<" ";
//	g<<"\nCostul minim: "<<cost[y];
}
return 0;
}
``````