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

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

Восстановить пароль Регистрация
 
Niсe
 Аватар для Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
08.01.2012, 00:44     Покрашенный граф #1
Привет
для вот такого условия
Дан ориентированный граф, у которого каждая дуга покрашена в один из трех цветов. Требуется найти длину кратчайшего пути из 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 тестов.
Помогите если есть глазастые что не так.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.01.2012, 00:44     Покрашенный граф
Посмотрите здесь:

C++ Граф
Граф C++
C++ Граф
Граф C++
C++ Граф в С
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.01.2012, 01:39     Покрашенный граф #2
Вот Вам тест в помощь:
5 5
2 5 1
3 5 3
2 3 2
1 2 1
4 2 2
Правильный ответ - 3
Niсe
 Аватар для Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
08.01.2012, 15:29  [ТС]     Покрашенный граф #3
спасибо!
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.01.2012, 17:16     Покрашенный граф #4
Цитата Сообщение от Niсe Посмотреть сообщение
спасибо!
Не за что. Как поймете, что алгоритм применяемый Вами не подходит, обращайтесь, помогу.
Niсe
 Аватар для Niсe
1 / 1 / 0
Регистрация: 09.12.2009
Сообщений: 30
08.01.2012, 18:57  [ТС]     Покрашенный граф #5
Цитата Сообщение от 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
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.01.2012, 23:23     Покрашенный граф #6
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. Если нет, то ответ минимальное значение из трех.
Yandex
Объявления
08.01.2012, 23:23     Покрашенный граф
Ответ Создать тему
Опции темы

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