# Cod sursa(job #20330)

Utilizator Data 21 februarie 2007 09:20:57 Traseu 0 cpp done Arhiva de probleme 1.81 kb
``````#include<stdio.h>
#define dim 61

int n,m,a[dim][dim];
int t[dim],s[dim],g[dim],gi[dim];
int c[dim][dim];
int sol[dim],nr=0;
void citire();
void DF(int );
void DFE(int );
void afisare();

int main()
{
freopen("traseu.in","r",stdin);
freopen("traseu.out","w",stdout);
int i;
citire();
afisare();
return 0;
}
void citire()
{
int x,y,i,j,z;
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&z);

g[x]++; gi[y]++;
a[x][y]=1;
c[x][y]=z;
}
for(i=1;i<=n;i++)
g[i]+=gi[i];
//for(i=1;i<=n;i++)
//printf("%d ",g[i]);

int max=-32000;
for(i=1;i<=n;i++)
if(g[i]>max)
max=g[i];
DF(max);
DFE(max);
/*
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d ",a[i][j]);
printf("\n");
}
printf("\n");
*/
}
void DF(int nod)
{
int i;
//printf("%d ",nod);
//printf("\n");
s[nod]=1;
for(i=1;i<=n;i++)
if(a[nod][i] && !s[i])
{
t[i]=nod;
DF(i);
}
}
void DFE(int nod)
{
//printf("%d ",nod);
sol[++nr]=nod;
int i;
for(i=1;i<=n;i++)
if(a[nod][i])
if(t[nod]!=i && t[i]!=nod)
{
a[nod][i]=0;
DFE(i);
}
for(i=1;i<=n;i++)
if(a[nod][i])
{
a[nod][i]=0;
DFE(i);
}
}
void afisare()
{
int i,j;
int suma=0;
//sol[nr+1]=1;
//nr+=1;
//printf("%d\n",nr);
//for(i=1;i<=nr;i++)
//printf("%d ",sol[i]);

//printf("\n");
for(i=1;i<nr;i++)
suma+=c[sol[i]][sol[i+1]];
printf("%d",suma);

}
``````