WA#12
Posted by
Carbon 30 Jan 2008 01:15
My program doesn't work on this test. Please, tell me what's wrong with it:
#include <stdio.h>
int C[500][500],R[500][500],U[500],T[500];
int main(int argc, char* argv[])
{
int N,M,start,finish,s,a,b,c,S,F,i,j,u;
scanf("%d%d",&N,&M);
start=N;
s=N-1;
for (i=0;i<M;i++)
{
scanf("%d%d%d",&a,&b,&c);
C[a-1][b-1]=c;
T[a-1]++;
}
scanf("%d%d",&S,&F);
S--;
F--;
U[s]=F;
for (i=0;i<N;i++)
if (i!=S&&i!=F&&T[i]==0)
{
s--;
U[s]=i;
}
do
{
finish=start-1;
start=s;
for (i=finish;i>=start;i--)
{
b=U[i];
for (j=0;j<N;j++)
if (C[j][b]!=0&&j!=S)
{
T[j]--;
if (T[j]==0)
{
s--;
U[s]=j;
}
}
}
}
while (s<start);
U[0]=S;
for (i=0;i<N;i++)
{
a=U[i];
for (j=0;j<N;j++)
R[i][j]=C[a][j];
}
for (i=0;i<N;i++)
{
b=U[i];
U[i]=-1;
for (j=0;j<N;j++)
C[j][i]=R[j][b];
}
U[N-1]=0;
for (i=N-2;i>=0;i--)
{
for (j=i+1;j<N;j++)
if (C[i][j]!=0&&U[j]!=-1)
{
u=C[i][j]+U[j];
if (u>U[i])
U[i]=u;
}
}
if (U[0]==-1)
printf("No solution");
else
printf("%d",U[0]);
return 0;
}