Shivraja GV Ответов: 3

Мне нужен алгоритм для следующего вопроса.я пытался, но это дает ошибку для некоторых входов

В вашей стране есть N городов и N-1 дорог, соединяющих пары городов таким образом, что существует путь между любой парой городов. Для каждой дороги вам дается ее плата, то есть сумма денег, которую вы должны заплатить, чтобы пересечь ее. Стоимость проезда из города в город-это сумма дорожных сборов на пути из пункта А в пункт Б.

Вам дается Q запросов для обработки. Существует два типа запросов:
1) 0 С :из-за инфляции плата за проезд по всем дорогам, прилегающим к городу " с " (все дороги, имеющие в качестве одной из своих конечных точек), умножается на 2.
2) 1 x y:вам необходимо найти стоимость путешествия от "x" до "y".
входной сигнал образца:
5 3
0 1 4
1 2 3
2 3 2
3 4 5
1 0 4
0 2
1 0 4
выход:
14
19

Объяснение:
В первом запросе расстояние равно 4+3+2+5=14

В первом запросе расстояние равно 4+6+4+5=19

Что я уже пробовал:

I=input()
n,q=list(map(int,I.split()))
city=list(range(n))
cost=[0]*(n-1)
while n!=1:
    I=input()
    l,r,c=list(map(int,I.split()))
    cost[l]=c
    n=n-1
while q:
    I=input()
    total=0
    q_list=list(map(int,I.split()))
    if(q_list[0]==0):
        i_1=city.index(q_list[1])
        if(i_1!=0 and i_1!=n-1):
            cost[i_1]=cost[i_1]*2
            cost[i_1-1]=cost[i_1-1]*2
        elif(i_1==0):
            cost[0]=cost[0]*2
        else:
            cost[n-2]=cost[n-2]*2
    else:
        total=sum(cost[q_list[1]:q_list[2]:1])
        print(total)
    q-=1

Patrice T

Показать пример ввода с фактическим и ожидаемым результатом.

Shivraja GV

пример ввода и вывода упоминается выше

Patrice T

а реальный результат ?

3 Ответов

Рейтинг:
1

OriginalGriff

Компиляция не означает, что ваш код верен! :смеяться:
Подумайте о процессе разработки как о написании электронного письма: успешная компиляция означает, что вы написали электронное письмо на правильном языке - например, на английском, а не на немецком, - а не то, что письмо содержало сообщение, которое вы хотели отправить.

Итак, теперь вы входите во вторую стадию разработки (на самом деле это четвертая или пятая, но вы перейдете к более ранним стадиям позже): тестирование и отладка.

Начните с рассмотрения того, что он делает, и как это отличается от того, что вы хотели. Это важно, потому что это дает вам информацию о том, почему он это делает. Например, если программа предназначена для того, чтобы позволить пользователю ввести число, а он удваивает его и печатает ответ, то если ввод / вывод был таким:

Input   Expected output    Actual output
  1            2                 1
  2            4                 4
  3            6                 9
  4            8                16
Тогда совершенно очевидно, что проблема заключается в бите, который удваивает его - он не прибавляет себя к себе или умножает его на 2, он умножает его на себя и возвращает квадрат входного сигнала.
Таким образом, вы можете посмотреть на код, и очевидно, что он находится где-то здесь:
int Double(int value)
   {
   return value * value;
   }

Как только у вас появится идея, что может пойти не так, начните использовать отладчик, чтобы выяснить, почему. Поместите точку останова в первую строку метода и запустите приложение. Когда он достигнет точки останова, отладчик остановится и передаст управление вам. Теперь вы можете запускать свой код построчно (так называемый "одноступенчатый") и просматривать (или даже изменять) содержимое переменных по мере необходимости (черт возьми, вы даже можете изменить код и повторить попытку, если вам это нужно).
Подумайте о том, что должна делать каждая строка кода перед ее выполнением, и сравните это с тем, что она действительно делала, когда вы использовали кнопку "Step over" для выполнения каждой строки по очереди. Он сделал то, что вы ожидали? Если да, то переходите к следующей строке.
Если нет, то почему? Чем это отличается?
Надеюсь, это поможет вам определить, в какой части этого кода есть проблема и в чем она заключается.
Это навык, и его стоит развивать, поскольку он помогает вам как в реальном мире, так и в развитии. И, как и все навыки, он только улучшается при использовании!

Рейтинг:
1

CPallini

Здесь: Проблема коммивояжера - Википедия[^] вы можете найти некоторые алгоритмы.

Рейтинг:
0

Patrice T

Прежде всего, это хорошая идея, чтобы дать ссылку на проблемную страницу. В этих сложных задачах сайта каждая деталь имеет значение.
Вы слишком упростили это требование:
- Никто тебе не говорил тот все города связаны по порядку создание дороги как лента.
Нарисуйте города по кругу, любой возможный способ связать города действителен до тех пор, пока все города связаны;
Это может быть лента в порядке 0-1-2-3-4.
Это может быть лента из порядка 0-2-4-1-3. и любого другого порядка.
Это может быть звезда (все дороги начинаются из одного города) 0-2, 1-2, 2-3, 2-4.
и так далее.
Поездка может быть между любыми 2 городами в любом порядке 0-4, 4-0, 1-3, 4-2 ...

Цитата:
Мне нужен алгоритм для следующего вопроса.

В основном это обход графа между 2 узлами. Вы должны найти, какой путь идет между 2 городами.
Города-это узлы, дороги-это края.
Обход графа - Википедия[^]
Попробуйте этот образец:
sample input:
5 3
0 2 4
1 2 3
2 3 2
2 4 5
1 0 4
output:
9