# Cod sursa(job #20325)

Utilizator Data 21 februarie 2007 08:56:15 Traseu 0 cpp done Arhiva de probleme 1.64 kb
``````#include<stdio.h>
#define dim 61

int n,m,a[dim][dim];
int t[dim],s[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();
for(i=1;i<=n;i++)
DF(i);
for(i=1;i<=n;i++)
DFE(i);
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);

a[x][y]=a[y][x]=1;
c[x][y]=c[y][x]=z;
}
/*
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]=a[i][nod]=0;
DFE(i);
}
for(i=1;i<=n;i++)
if(a[nod][i])
{
a[nod][i]=a[i][nod]=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);

}
``````