Покрашенный граф

@Niсe · Регистрация: 09.12.2009

Студворк — интернет-сервис помощи студентам

Привет
для вот такого условия
Дан ориентированный граф, у которого каждая дуга покрашена в один из трех цветов. Требуется найти длину кратчайшего пути из 1й вершины в N-ую, если в пути не могут идти подряд две дуги одного цвета.

Входные данные
В первой строке записаны N и M (2<=N<=200, 0<=M<=N*N). Далее идет M строк с описанием дуг. Каждая дуга описывается тремя целыми числами X, Y, C - дуга из вершины X в вершину Y покрашена в цвет C (1<=X,Y<=N, 1<=C<=3). Между каждой парой вершин не может быть более одной дуги в одном направлении.

Выходные данные
Выходные данные. Выведите длину кратчайшего пути из 1й вершины в N-ую. Если пути не существует, то выведите -1.

Пример

Ввод

Пример #1
4 4
1 2 1
2 3 2
3 4 3
2 4 1

Пример #2

3 2
1 2 1
2 3 1

Вывод

Пример №1
3

Пример №2
-1

написал код:

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
#include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    #include <iostream>
    #include <vector>
    #include <string>
    #include <queue>
    using namespace std;
    const int INF = 1000000;
    void BFS(vector <int> &d, vector <int> &p, int n, vector<vector<int>> next, int col[202][202])
    {
        int temp = 0;
        d = vector <int> (n, INF);
        d[n-1] = 0;
        p = vector<int>(n, -1);
        p[n-1] = n-1;
        queue <int> q;
        q.push(n-1);
        while (!q.empty())
        {
            int v = q.front();
            q.pop();
            for(unsigned int i = 0; i< next[v].size(); i++)
            {
                int u = next[v][i];
                bool ult = false;
                for(int j = 0; j<n; j++)
                    if((col[u][j]!=0)&&(col[u][j]!=col[v][u])||(u==0))
                        ult = true;
                if((p[u]==-1)&&(ult))
                {
                    p[u] = v;
                    d[u] = d[v]+1;
                    q.push(u);                   
                }
            }
        }
    }
    int main()
    {
        vector <int> d;
        vector<int> p;
        int a=0,b=0,c=0,m=0,n=0;
        cin>>n>>m;
        vector<vector<int>> next(202);
        int col [202][202];
        memset(col,0,sizeof(col));
        for(int i = 0; i < m; i++)
            {
                cin>>a>>b>>c;
                next[b-1].push_back(a-1);
                col[b-1][a-1] = c;
            }
        BFS(d, p, n, next, col);
        if(d[0]!=INF && m!=0)cout<<d[0];
        else cout<<"-1";
 
    return 0;
    }

Так вот видимо я что-то не учел, а что не могу понять. Программа проходит 9 из 20 тестов.
Помогите если есть глазастые что не так.

valeriikozlov · 08.01.2012, 01:39

Вот Вам тест в помощь:
5 5
2 5 1
3 5 3
2 3 2
1 2 1
4 2 2
Правильный ответ - 3

@Niсe · 08.01.2012, 15:29 **[ТС]**

спасибо!

valeriikozlov · 08.01.2012, 17:16

Сообщение от Niсe

спасибо!

Не за что. Как поймете, что алгоритм применяемый Вами не подходит, обращайтесь, помогу.

@Niсe · 08.01.2012, 18:57 **[ТС]**

Сообщение от valeriikozlov

Не за что. Как поймете, что алгоритм применяемый Вами не подходит, обращайтесь, помогу.

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
  #include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    #include <iostream>
    #include <vector>
    #include <string>
    #include <queue>
    using namespace std;
    const int INF = 1000000;
    void BFS(vector <int> &d, vector <int> &p, int n, vector<vector<int>> next, int col[202][202])
    {
        d = vector <int> (n, INF);
        d[n-1] = 0;
        p = vector<int>(n, -1);
        p[n-1] = n-1;
        queue <int> q;
        q.push(n-1);
        int temp = 0;
        while (!q.empty())
        {
            int v = q.front();
            q.pop();
            for(unsigned int i = 0; i< next[v].size(); i++)
            {
                int u = next[v][i];
                bool ult = false;
                    if((temp!=col[v][u]||temp == 0)||(u==0))
                        ult = true;
                if((p[u]==-1)&&(ult))
                {
                    p[u] = v;
                    d[u] = d[v]+1;
                    q.push(u);  
                    temp = col[v][u];
                }
            }
        }
    }
    int main()
    {
        vector <int> d;
        vector<int> p;
        int a=0,b=0,c=0,m=0,n=0;
        cin>>n>>m;
        vector<vector<int>> next(202);
        int col [202][202];
        memset(col,0,sizeof(col));
        for(int i = 0; i < m; i++)
            {
                cin>>a>>b>>c;
                next[b-1].push_back(a-1);
                col[b-1][a-1] = c;
            }
        BFS(d, p, n, next, col);
        if(d[0]!=INF && m!=0)cout<<d[0];
        else cout<<"-1";
        cin>>n;
    return 0;
    }

исправил на вот так, все равно 2
подскажите пожалуйста

valeriikozlov · 08.01.2012, 23:23

Niсe, У Вас реализацию поиска в ширину. Для этой задачи любой существующий алгоритм в оригинальном виде не подойдет. Нужно переделывать его под эту задачу.
Представьте себе вершину (допустим через нее проходит самый короткий путь) - в которую входят 3 дуги (по одной каждого цвета) и из которой выходят 3 дуги (по одной каждого цвета). Допустим Вы дошли быстрее всего в эту вершину через дугу цветом 1. Вы ее помечаете, и идете дальше по двум дугам: 2 и 3 цветов. Путь в эту же вершину через дугу 2 хоть и дольше чем через дугу 1, но он дает возможность идти дальше из этой вершины по дуге 1 и в итоге может оказаться что это и есть самый короткий путь.
Для этой задачи подойдет поиск в ширину, но:
- рассматривайте вершину не как единое целое, а как три разных составляющих (по цветам). Например вершину 4, рассматривайте как: (4,1), (4,2), (4,3). Здесь второе число считается номером цвета. Для каждой такой составляющей будет свое значение. Например: (4,1)=15, (4,2)=15, (4,3)=17. Это будет значить, что вершину 4 по дугам 1 и 2 цвета мы достигли за 15 шагов, а по дуге цветом 3, мы достигли за 17 шагов.
Изначально помещайте в очередь не просто вершину n-1, а вот так: (n-1,1), (n-1,2), (n-1, 3), поставив им метки 0 (будем считать, что вершину, из которой начинаем путь мы по всем вершинам достигли за 0 шагов).
Далее алгоритм такой:
Из очереди берете очередной элемент, например: (4,2). Смотрите смежные вершины с 4 вершиной, (например смежная вершина 3). Если смежная вершина соединена не дугой цветом 2 (например цветом 1), то: (3,1), если она не помечена, помечаете значением (4,2)+1 и заносите в очередь.
В конце этого алгоритма проверяете значения (0,1), (0,2), (0,3). Если все три значения не помечены, то ответ: -1. Если нет, то ответ минимальное значение из трех.

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	08.01.2012, 01:39
	Вот Вам тест в помощь: 5 5 2 5 1 3 5 3 2 3 2 1 2 1 4 2 2 Правильный ответ - 3 1

@Niсe 1 / 1 / 0 Регистрация: 09.12.2009 Сообщений: 30
	08.01.2012, 15:29 [ТС]
	спасибо! 0

valeriikozlov 4728 / 2549 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	08.01.2012, 23:23
	Niсe, У Вас реализацию поиска в ширину. Для этой задачи любой существующий алгоритм в оригинальном виде не подойдет. Нужно переделывать его под эту задачу. Представьте себе вершину (допустим через нее проходит самый короткий путь) - в которую входят 3 дуги (по одной каждого цвета) и из которой выходят 3 дуги (по одной каждого цвета). Допустим Вы дошли быстрее всего в эту вершину через дугу цветом 1. Вы ее помечаете, и идете дальше по двум дугам: 2 и 3 цветов. Путь в эту же вершину через дугу 2 хоть и дольше чем через дугу 1, но он дает возможность идти дальше из этой вершины по дуге 1 и в итоге может оказаться что это и есть самый короткий путь. Для этой задачи подойдет поиск в ширину, но: - рассматривайте вершину не как единое целое, а как три разных составляющих (по цветам). Например вершину 4, рассматривайте как: (4,1), (4,2), (4,3). Здесь второе число считается номером цвета. Для каждой такой составляющей будет свое значение. Например: (4,1)=15, (4,2)=15, (4,3)=17. Это будет значить, что вершину 4 по дугам 1 и 2 цвета мы достигли за 15 шагов, а по дуге цветом 3, мы достигли за 17 шагов. Изначально помещайте в очередь не просто вершину n-1, а вот так: (n-1,1), (n-1,2), (n-1, 3), поставив им метки 0 (будем считать, что вершину, из которой начинаем путь мы по всем вершинам достигли за 0 шагов). Далее алгоритм такой: Из очереди берете очередной элемент, например: (4,2). Смотрите смежные вершины с 4 вершиной, (например смежная вершина 3). Если смежная вершина соединена не дугой цветом 2 (например цветом 1), то: (3,1), если она не помечена, помечаете значением (4,2)+1 и заносите в очередь. В конце этого алгоритма проверяете значения (0,1), (0,2), (0,3). Если все три значения не помечены, то ответ: -1. Если нет, то ответ минимальное значение из трех. 1