Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
sera772
0 / 0 / 0
Регистрация: 04.12.2012
Сообщений: 11
#1

Задача с Olympiads - C++

07.01.2013, 22:48. Просмотров 449. Ответов 6
Метки нет (Все метки)

Вроде работает, но на половине тестов срезается...
Условие:
В столице одной небольшой страны очень сложная ситуация. Многокилометровые пробки буквально парализовали движение в городе, и власти на многих улицах ввели одностороннее движение, не анализируя, можно ли будет теперь проехать из любого места в городе в любое другое, не нарушая правила. Транспортная система столицы представляет собой N площадей, соединенных M полосами для движения, в том числе круговыми полосами, проходящими по площади. Каждая полоса предназначена для движения только в одну определенную сторону. По круговой полосе можно двигаться только внутри площади и только против часовой стрелки.
Власти города на каждой полосе разместили видеокамеру, поэтому если Андрей едет по встречной полосе (при её наличии) или, в случае одностороннего движения, в сторону противоположную предписанной знаками, то после поездки против правил по каждой из полос ему придется заплатить штраф в размере одной тысячи тугриков этой страны.
Андрей, который торопится купить товар со скидкой, решил доехать до магазина в любом случае, даже если для этого придется нарушать правила. Но он хочет выбрать такой маршрут движения, суммарный штраф на котором минимален.
Андрей ещё не решил, откуда именно и в какой магазин он собирается ехать, поэтому ему необходимо ответить на несколько вопросов вида "Какой минимальный штраф надо заплатить, чтобы добраться из пункта А в пункт В?". Отвечая на потребности жителей столицы, известная поисковая система Индекс разрабатывает соответствующий сервис.
Помогите этой поисковой системе.
Формат входных данных:
В первой строке входных данных содержатся два числа N и M - количество площадей и полос движения в городе соответственно (1 <= N <= 5000, 1 <= M <= 10000). Далее содержатся описания полос, по которым движение разрешено. Каждая полоса описывается номерами двух площадей, которые она соединяет. Движение разрешено в направлении от первой из указанных площадей ко второй.
В следующей строке содержится одно число К - количество вопросов у Андрея (1 <= k <= 10000, N*K <= 2 * 10^7). В следующих строках описываются вопросы, каждый вопрос описывается номерами двух площадей, между которыми требуется найти дешевый путь. Путь необходимо продолжить от первой из указанных площадей ко второй.
Формат выходных данных:
Для каждого вопроса выведите одно число - искомый минимальный размер штрафа в тысячах тугриков. В случае, если пути между выбранной парой площадей не существует, выведите "-1".

Пример:
Входные данные:
5 5
2 1
2 4
3 2
4 3
5 4
3
5 1
1 5
2 3

Выходные данные:
0
2
0

Мое решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
int N,M,K,dor[5000][5000],j,u,rez,min[5000];
 
int hod(int uk,int sum)
{int i;
 
if (rez==0)
    return 0;
if (uk==u-1)
{
    if (rez>sum)
        rez=sum;
    return 1;
};
 
if (sum>=rez)
    return 0;
 
if (sum<min[uk])
    min[uk]=sum;
for (i=0;i<N;i++)
{
    if (dor[uk][i]>=0&&sum+dor[uk][i]<min[i])
        hod(i,sum+dor[uk][i]);
}
    return 0;
}
 
int main()
{ int i;
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d %d",&N,&M);
 
for (i=0;i<5000;i++)
    for (j=0;j<5000;j++)
        dor[i][j]=-1;
for (i=0;i<M;i++)
{
scanf("%d %d",&j,&u);
if (dor[j-1][u-1]==-1)
{
    dor[j-1][u-1]=0;
    dor[u-1][j-1]=1;
}
else
{
    dor[j-1][u-1]=0;
    dor[u-1][j-1]=0;
};
};
scanf("%d",&K);
for (i=0;i<K;i++)
{
rez=20000;
                for (j=0;j<N;j++)
            min[j]=20000;
    scanf("%d %d",&j,&u);
    hod(j-1,0);
    if (rez==20000)
    {printf("-1\n");}
    else printf("%d\n",rez);
}
return 0;
}
Буду благодарен помощи!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.01.2013, 22:48
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Задача с Olympiads (C++):

Задача с olympiads.ru - C++
Всем привет. Столкнулся с проблемой при решении задачи E &quot;Распродажа&quot; с сайла olympiads.ru...

Задача: В некотором государстве ввели компьютерный паспорт гражданина.(задача) - Pascal
Доброго времени суток,форумчане. Хотелось бы попросить помощи в решении одной задачи от умных голов. Задача: В некотором...

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника - PascalABC.NET
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он уплатил по 31 талеру, а за каждого быка по...

Задача на k-тую цифру последовательности, задача на схему Горнера. - Pascal
Ну, собственно опять прошу помощи... Задача 1: Определить k-тую цифру последовательности 1234567891011121314…, в которой выписаны подряд...

Первая смешанная задача для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье - Дифференциальные уравнения
Решить первую смешанную задачу для волнового уравнения на отрезке (задача о колебаниях ограниченной струны) методом Фурье ...

Задача о размещении весов по ящикам (задача о рюкзаках) - Delphi
Есть упорядоченный по невозрастанию набор весов предметов w1..wn, которые необходимо распределить по ящикам способным выдержать вес V,...

6
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.01.2013, 23:36 #2
Цитата Сообщение от sera772 Посмотреть сообщение
Вроде работает, но на половине тестов срезается...
Что значит срезается? Не проходит по времени? Или неправильные ответы выдает?
Если не проходит по времени, то вот что нужно переделать:
Ваш код для каждой площади вычисляет результат несколько раз в массив min[5000] (ведь количество площадей намного меньше количества вопросов). Быстрее будет, если создадите массив min[5000][5000], заранее просчитаете туда все возможные результаты. А потом сразу будете выдавать ответы. Причем если уже посчитано для площади номер 0, то эти результаты можете учитывать при вычислении результатов для других площадей.
1
sera772
0 / 0 / 0
Регистрация: 04.12.2012
Сообщений: 11
08.01.2013, 00:46  [ТС] #3
Выдает неправильный ответ на тестах, где N<=10, M<=20. На тестах, где N<=2000, M<=3000, K=1 выдает правильный ответ. В чем может быть причина?
Возможно дело в компиляторе я пишу на visual c++, а там стоит gcc 4.7.2?
0
valeriikozlov
Эксперт С++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.01.2013, 01:02 #4
Цитата Сообщение от sera772 Посмотреть сообщение
Возможно дело в компиляторе я пишу на visual c++, а там стоит gcc 4.7.2?
вряд ли. ссылку на задачу дать можете?

Добавлено через 10 минут
см комментарии:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int main()
{ 
    int i;
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d %d",&N,&M);
 
    for (i=0;i<5000;i++)
        for (j=0;j<5000;j++)
            dor[i][j]=-1;
    for (i=0;i<M;i++)
    {
        scanf("%d %d",&j,&u);
        if (dor[j-1][u-1]==-1)
        {
            dor[j-1][u-1]=0;
            dor[u-1][j-1]=1;
        }
        else
        {
            dor[j-1][u-1]=0;
            dor[u-1][j-1]=0;// вот это неправильно, эту строку закоментируйте
        };
    };
    scanf("%d",&K);
    for (i=0;i<K;i++)
    {
        rez=20000;
        for (j=0;j<N;j++)
            min[j]=20000;
        scanf("%d %d",&j,&u);
        hod(j-1,0);
        if (rez==20000)
        {
            printf("-1\n");
        }
        else
            printf("%d\n",rez);
    }
return 0;
}
2
sera772
0 / 0 / 0
Регистрация: 04.12.2012
Сообщений: 11
08.01.2013, 01:30  [ТС] #5
Вот ссылка:
http://olympiads.ru/zaoch/2012-13/problems/index.shtml
Задача Н.
Насчет той строки я рассуждал так: если до объявления пути уже существовал путь в каком-либо направлении, то это будет двухполосное движение, следовательно, проехав по этой дороге, нарушить правила не получится, поэтому и обнулил.

Добавлено через 16 минут
Спасибо большое!!! Дело было как раз в этой строчке. Исправил условие, и все заработало!
0
lunohod-1
1 / 1 / 0
Регистрация: 14.12.2011
Сообщений: 44
21.01.2013, 21:36 #6
Чтобы не начинать новую тему, напишу тут.
Пытаюсь решить задачу B "Страусиная ферма"
(из тех же задач)
Но проблема в том, что был выбран метод перебора. И если на первых 10 тестах всё в порядке, у всех остальные получается очень большое время работы.

Если кто может и понял, как это сделать, намекните, может я что-то упустил и можно решить без полного перебора всех конфигураций?

P.S. Исходник не прилагаю, так там ничего хорошего, кроме огромного цикла с перебором всех квадратов, нет.
0
sera772
0 / 0 / 0
Регистрация: 04.12.2012
Сообщений: 11
21.01.2013, 22:05  [ТС] #7
Задача чисто на расчет. Я ее писал также на перебор, но нужно его упростить. Рассчитай минимальные значения длины и ширины и пляши дальше от них. В одном случае будет длина<ширины, в другом >=. Рассчитай для обоих случаев значения. Получится 2 перебора, но сокращенных. В общем и целом, реши задачу математически на приведенных примерах.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.01.2013, 22:05
Привет! Вот еще темы с ответами:

Задача линейного программирования, транспортная задача - Методы оптимизации
Всем привет. сижу на экзамене, помогите пожалуйста решить,сроно!!! заранее спасибо.

Задача Дам или задача Восьми - Алгоритмы
помогите найти ошибку в алгоритме. не находит ответ подозреваю ошибку в k, i, j package com.company; import java.util.Arrays;...

Задача на файл и задача на создание очереди - Pascal
1 Дан символьный файл, содержащий, по крайней мере, один символ пробела. Удалить из файла все символы, предшествующие пробелу 2 ...

задача Коши и краевая задача - Matlab
Помогите кто чем может))


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Yandex
Объявления
21.01.2013, 22:05
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru