Cod sursa(job #20324)

Utilizator rusRus Sergiu rus Data 21 februarie 2007 08:54:31
Problema Traseu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 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);
    
    citire();
    DF(1);
    DFE(1);
    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);

}