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

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

Восстановить пароль Регистрация
 
sera772
0 / 0 / 0
Регистрация: 04.12.2012
Сообщений: 11
07.01.2013, 22:48     Задача с Olympiads #1
Вроде работает, но на половине тестов срезается...
Условие:
В столице одной небольшой страны очень сложная ситуация. Многокилометровые пробки буквально парализовали движение в городе, и власти на многих улицах ввели одностороннее движение, не анализируя, можно ли будет теперь проехать из любого места в городе в любое другое, не нарушая правила. Транспортная система столицы представляет собой 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;
}
Буду благодарен помощи!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.01.2013, 22:48     Задача с Olympiads
Посмотрите здесь:

C++ Задача с olympiads.ru

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
07.01.2013, 23:36     Задача с Olympiads #2
Цитата Сообщение от sera772 Посмотреть сообщение
Вроде работает, но на половине тестов срезается...
Что значит срезается? Не проходит по времени? Или неправильные ответы выдает?
Если не проходит по времени, то вот что нужно переделать:
Ваш код для каждой площади вычисляет результат несколько раз в массив min[5000] (ведь количество площадей намного меньше количества вопросов). Быстрее будет, если создадите массив min[5000][5000], заранее просчитаете туда все возможные результаты. А потом сразу будете выдавать ответы. Причем если уже посчитано для площади номер 0, то эти результаты можете учитывать при вычислении результатов для других площадей.
sera772
0 / 0 / 0
Регистрация: 04.12.2012
Сообщений: 11
08.01.2013, 00:46  [ТС]     Задача с Olympiads #3
Выдает неправильный ответ на тестах, где N<=10, M<=20. На тестах, где N<=2000, M<=3000, K=1 выдает правильный ответ. В чем может быть причина?
Возможно дело в компиляторе я пишу на visual c++, а там стоит gcc 4.7.2?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.01.2013, 01:02     Задача с Olympiads #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;
}
sera772
0 / 0 / 0
Регистрация: 04.12.2012
Сообщений: 11
08.01.2013, 01:30  [ТС]     Задача с Olympiads #5
Вот ссылка:
http://olympiads.ru/zaoch/2012-13/problems/index.shtml
Задача Н.
Насчет той строки я рассуждал так: если до объявления пути уже существовал путь в каком-либо направлении, то это будет двухполосное движение, следовательно, проехав по этой дороге, нарушить правила не получится, поэтому и обнулил.

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

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

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

Текущее время: 08:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru