Матрица расстояний.С++ Опции

[Krjuger]

Дан граф. Требуется построить для него матрицу расстояний. Если пути не существует, тщ елемент матрици равен -1.Для висячих вершин (вершин степени 0) положим так же -1, для всех остальных вершин на диагонале положим 2.
Ввод: граф, представленный в формате FO. Размер графа не более 150 вершин.
Тобиш при вводе в программу.
5
0
3 4 0
2 5 0
2 5 0
3 4 0
я должен получить результат
-1 -1 -1 -1 -1
-1 2 1 1 2
-1 1 2 2 1
-1 1 2 2 1
-1 2 1 1 2
Задачу надо решить успользуя алгоритм Флойда.Для его использования надо исходные данные преобразовать в матрицу смежности,вот тут то у меня и возникли проблемы.

#pragma hdrstop
#pragma argsused
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

const int INF = 100*1000*1000;

int main()
{
        // считываем матрицу графа
        int n;
		int t;
        cin >> n;
        vector < vector<int> > g (n, vector<int> (n));
        for (int i=0; i<n; i++)
	{  
		do
		{
		cin >> t;
	                for (int j=0; j<n; j++)
                               {
		      if (j==i)
		      {
		         if (t==0)
		        {
		        g[i][j] = t ? t : INF;
                                         }
		         else
		         {
                                                g[i][j] = 2;
		          }
		       }
	   	       else
		      {
			if (j==(t-1))
			{
			        g[i][j] =1;
			}
						
		        }
		}
	}
	while (t!=0);
         }
 
        // собственно алгоритм
        // храним две матрицы: для текущего шага и от предыдущего шага
        vector<vector<int> > d (n), d2;
        d2 = g;
        for (int i=0; i<n; i++)
                d[i].resize (n+1);
       for (int k=0; k<n; ++k)
    	for (int i=0; i<n; ++i)
	    	for (int j=0; j<n; ++j)
		    	if (d[i][k] < INF && d[k][j] < INF)
				d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
 
        // выводим результат
        for (int i=0; i<n; i++)
        {
                for (int j=0; j<n; j++)
                        cout << (d[i][j]<INF ? d[i][j] : -1) << ' ';
                cout << endl;
        }
}

Как я не старался получить что либо более сносное,ничего не вышло,поэтому прошу помощи.

[volvo]

Ну, ты б для начала проверил, правильно ли заполняется матрица смежности. Я бы сделал так:

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

const int INF = 100*1000*1000;

int main()
{
    // считываем матрицу графа
    int n;
    int t;
    cin >> n;

    vector < vector<int> > g (n, vector<int> (n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            g[i][j] = (i == j) ? 0 : INF;
        }

    for (int i=0; i<n; i++)
    {
        do
        {
            cin >> t;
            if(t)
            {
                g[i][t-1] = 1;
            }
        }
        while (t!=0);
    }

    // собственно алгоритм
    vector < vector<int> > d (n, vector<int> (n));
    d = g;

    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                if(d[i][k] < INF && d[k][j] < INF)
                {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }

    // выводим результат
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
            cout << (d[i][j]<INF ? d[i][j] : -1) << ' ';
        cout << endl;
    }
    return 0;
}

На твоих входных данных выдает:

0 -1 -1 -1 -1
-1 0 1 1 2
-1 1 0 2 1
-1 1 2 0 1
-1 2 1 1 0

(элементы главной диагонали были сброшены в ноль, по привычке. Можешь потом пройтись по матрице и заполнить их чем угодно.)

[Krjuger]

Спасибо огромное,я изначально понимал,что именно в преобразовани в смежную матрицу у меня проблемы.Но вот самому исправить не вышло.На необходимое мне значение на диагонали я поменял,но тут с приведенными тобой исправлениями все равно выходит небольшая накладка.По условию,если точка висячая,тобиш не соединяется с другими,то ее значение должно быть -1,а в приведенном коде выходит 0 т.к. лежит на диагонали.Я согласен что это бред,но таково задание.
В общем я чуть чуть изменил под свои требования и вышло вот так.

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

const int INF = 100*1000*1000;

int main()
{
    // считываем матрицу графа
    int n;
    int t;
    cin >> n;

    vector < vector<int> > g (n, vector<int> (n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            g[i][j] = (i == j ) ? 2 : INF;
        }

    for (int i=0; i<n; i++)
    {
        do
        {
            cin >> t;
            if(t)
            {
                g[i][t-1] = 1;
            }
			else
             g[i][t]=INF;  //вот тут пришлось добавить 
        }
        while (t!=0);
	}

    // собственно алгоритм
    vector < vector<int> > d (n, vector<int> (n));
    d = g;

    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                if(d[i][k] < INF && d[k][j] < INF)
                {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }

    // выводим результат
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
            cout << (d[i][j]<INF ? d[i][j] : -1) << ' ';
        cout << endl;
    }
    return 0;
}

[Krjuger]

Так,я немного погорячился,так что то что в предыдущем после не решает мою,проблему,так что буду думать пока то сам.Как идея ввести переменную в которой будет храниться позиция переменной t,если t=0 и позиция ее 1 то вершина висячая и элемент на диагонали равен -1,а если позиция не первая, то как минимум с 1 вершиной данная соединена ребром и значит на диагонали будет 2.Щас попробую это реализовать.

Добавлено через 9 мин.
В общем,в итоге вот программа,которую я сдал.

#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

const int INF = 100*1000*1000;

int main()
{
    // считываем матрицу графа
    int n;
    int t;
    cin >> n;

    vector < vector<int> > g (n, vector<int> (n));
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
        {
            g[i][j] = (i == j ) ? 2 : INF;
        }

    for (int i=0; i<n; i++)
    {
        do
        {  
            int pos_t;
            cin >> t;
            pos_t=1;
            if(t)
            {
                g[i][t-1] = 1;
            }
            else
            {
	if (pos_t==1)
	        g[i][i] = INF;
             }
         pos_t++;
        }
        while (t!=0);
	}

    // собственно алгоритм
    vector < vector<int> > d (n, vector<int> (n));
    d = g;

    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)
                if(d[i][k] < INF && d[k][j] < INF)
                {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }

    // выводим результат
    for (int i=0; i<n; i++)
    {
        for (int j=0; j<n; j++)
            cout << (d[i][j]<INF ? d[i][j] : -1) << ' ';
        cout << endl;
    }
    return 0;
}