Visual Basic, .NET, ASP, VBScript
 

   
   
     

Форум - Олимпиады

Страница: 1 |

 

  Вопрос: Маршрут макисмальной длинны Добавлено: 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;

Паскаль - это хуже чем бэйсик.
Неправда ваша!
  1. 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 |

Поиск по форуму



© Copyright 2002-2011 VBNet.RU | Пишите нам