VBNet - Форум - Маршрут макисмальной длинны

Вопрос: Маршрут макисмальной длинны Добавлено: 06.01.12 18:42

Автор вопроса: Лёха | Web-сайт: supersait16.ucoz.ru

Привет.Есть неориентированый взвешеный граф, в нём надо найти самый длинный маршрут.Я сделал, код работает правильно, но ,когда N городов <=1000 улаживается во время выполнения, а дальше,когда N > 1000 выполняется довольно таки долго.А надо, чтоб для N = 32800 за секунду выполнялось.Вот код, помогите оптимизировать:

program test_4;
type TGraph = array of array of LongInt;
     TBoolList = array of boolean;
     TLIntList = array of Longint;
var
    G:TGraph;
    Visited:TBoolList;
    N:longint;
    X, Y, Z:longint;
    i, j:longint;
    Len:LongInt;

    Stack:TLIntList;
    N_El:longint;
    MaxLen:longint;

procedure PutEl(l:longint);
begin
    inc(N_El);
    Stack[N_El]:=l;
end;

function GetEl : longint;
begin
    if N_El > 0 then
    begin
        dec(N_El);
        GetEl:=Stack[N_El + 1];
    end;
end;

procedure DFS(V:longint);
var i: longint;
begin
    Visited[V]:=true;
    for i:=1 to N do
    begin
        if(G[V, i] > 0) and (not Visited[i]) then
        begin
            Len:=Len + G[V, i];
            PutEl(G[V, i]);
            DFS(i);
        end;
    end;
    if Len > MaxLen then
    begin
        MaxLen:=Len;
    end;
    Len:=Len - GetEl;
end;

procedure ResetData;
var i:longint;
begin
    for i:=1 to N do
    begin
        Visited[i]:=false;
    end;
    N_El:=0;
    Len:=0;
end;

begin
    assign(input, 'input.txt'); reset(input);
    readln(N);
    SetLength(G, N + 1, N + 1);
    SetLength(Visited, N + 1);
    SetLength(Stack, N + 1);

    for i:=1 to N do
    begin
        for j:=1 to N do
        begin
            G[i, j]:=0;
        end;
    end;

    j:=0; Len:=0; N_El:=0; MaxLen:=0;
    for i:=1 to N - 1 do
    begin
        readln(X, Y, Z);
        G[X, Y]:=Z;
        G[Y, X]:=Z;
        Visited[i]:=false;
    end;

    for i:=1 to N do
    begin
        DFS(i);
        ResetData;
    end;

    assign(output, 'output.txt');
    rewrite(output);
    writeln(MaxLen);
    Close(output);
    Close(input);
end.

Ответить

Ответы Всего ответов: 5

Номер ответа: 1 Автор ответа: EROS Вопросов: 58 Ответов: 4255	Профиль \| \| #1	Добавлено: 07.01.12 00:27
	if Len > MaxLen then begin MaxLen:=Len; end; Это даже еще хуже чем бейсик... прям ваще печалька.. Ответить

Номер ответа: 2 Автор ответа: Лёха Вопросов: 20 Ответов: 79	Web-сайт: supersait16.ucoz.ru Профиль \| \| #2	Добавлено: 07.01.12 12:56
	Да, ты прав. Паскаль - это хуже чем бэйсик. Но ничего не поделаешь, у нас на олимпиадах только паскаль. Ответить

Номер ответа: 3 Автор ответа: fAndOrIn Вопросов: 5 Ответов: 344	Профиль \| \| #3	Добавлено: 23.01.12 20:34
	if Len > MaxLen then begin MaxLen:=Len; end; Паскаль - это хуже чем бэйсик. Неправда ваша! if Len > MaxLen then MaxLen:=Len; Нормально всё пишется, когда смысл улавливаешь! Ответить

Номер ответа: 4 Автор ответа: К0ВAЛЄHK0 Вопросов: 0 Ответов: 22	Профиль \| \| #4	Добавлено: 21.08.12 14:35
	подскажи лутше как построить последовательность точек Брезенхейма Ответить

Номер ответа: 5 Автор ответа: К0ВAЛЄHK0 Вопросов: 0 Ответов: 22	Профиль \| \| #5	Добавлено: 21.08.12 14:35
	подскажи лутше как построить последовательность точек Брезенхейма Ответить

Страница: 1 |