Cod sursa(job #67629)

Utilizator floringh06Florin Ghesu floringh06 Data 25 iunie 2007 12:49:59
Problema Sate Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda Finala, Clasa a 9-a si gimnaziu Marime 2.28 kb
using namespace std;

#define MAX_N 1005
#define MAX_M 100030

#include <stdio.h>
#include <fstream>
#include <stdlib.h>

FILE *fin=fopen("sate.in","r"),
     *fout=fopen("sate.out","w");
     
typedef struct 
 {
   int x,y;
   int d;
 } data;
 
int a[MAX_N][MAX_N];
int x,y,n,m,sol=0;

void citire (void)
{ 
 int i,ok=0,px=0,py=0,d=0;
 fscanf(fin,"%d %d %d %d",&n,&m,&x,&y);
 for (i=1; i<=m; i++) {
   fscanf(fin,"%d %d %d",&px,&py,&d);
   if (py==x && px==y) { sol=d; ok=1; }
   a[px][py]=d;
  }
 if (ok==1) 
  {
    fprintf(fout,"%d\n",sol);
    return ;  
  }
}    

void precalculate (void)
{
 int i,j; 
 for (i=y; i<=n; i++)
  if (a[y][i]!=0)
     for (j=i+1; j<=n; j++)
      if (a[i][j]!=0) a[y][j]=a[y][i]+a[i][j];

 for (i=x; i<=n; i++)
  if (a[x][i]!=0)
     for (j=i+1; j<=n; j++)
      if (a[i][j]!=0) a[x][j]=a[x][i]+a[i][j];
      
 for (i=x; i>=1; i--) 
  if (a[i][x]!=0)
     for (j=i+1; j<=x; j++)     
      if (a[i][j]!=0) a[j][x]=a[i][x]-a[i][j];
 
 for (i=y; i>=1; i--) 
  if (a[i][y]!=0)
     for (j=i+1; j<=y; j++)     
      if (a[i][j]!=0) a[j][y]=a[i][y]-a[i][j];
      
}      

void solve (void)
{
  int i,px,py;   
  precalculate();
  if (a[x][y]!=0) 
   { sol=a[x][y]; return; }
  for (i=x; i<=y; i++)
   if (a[x][i]!=0 && a[i][y]!=0) 
    {
     sol=a[x][i]+a[i][y];
     return ;
    } 
  for (i=y+1; i<=n; i++)
   if (a[x][i]!=0 && a[y][i]!=0)
    {
      sol=a[x][i]-a[y][i];
      return ;
    }
  for (i=1; i<=x; i++)
   if (a[i][x]!=0 && a[i][y]!=0)
    {
      sol=a[i][y]-a[i][x];
      return ;
    } 
  for (i=1; i<=3001; i++)
    {
     px=rand() % (y-x+1);
     py=rand() % (y-px+1);
     if ((a[x][px]!=0)&&(a[px][py]!=0)&&(a[py][y]!=0))
      {
        sol=a[x][px]+a[px][py]+a[py][y];
        return ;
      }
     if ((a[x][py]!=0)&&(a[px][y]!=0)&&(a[px][py]!=0))
      {     
        sol=a[x][py]+a[px][y]-a[px][py];
        return ;
      }   
    }                        
}        
  
int main()
{
  citire();
  if (sol!=0) return 0;        
  solve();
  int i,j;
 /* for (i=1; i<=n; i++) {
    for (j=1; j<=n; j++)
     fprintf(fout,"%d ",a[i][j]);
    fprintf(fout,"\n");
  }*/  
  fprintf(fout,"%d\n",sol);
  
  fclose(fin);
  fclose(fout);
  return 0;
}