ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1450. Российские газопроводы

WA#12
Послано Carbon 30 янв 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;
}