ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1072. Маршрутизация

[Help me] What is Test#3
Послано [LTDT02]1112477 27 ноя 2012 08:30
My code...

#include <iostream>
#include <string>
using namespace std;

struct LAN
{
    int somay;
    char **IP;
    char **Sub;
};

int ChungMang(int a, int b, LAN *L);
void Dijkstra(LAN *L, int d[], int prev[], int label[], int dau, int cuoi, int somang,int &kq);
void Show(int dau, int cuoi, int prev[]);

void main ()
{
    int somang;
    cin>>somang;
    LAN *L;
    L= new LAN[somang+1];
    for(int i =1;i<=somang;i++)
    {
        cin>>L[i].somay;
        L[i].IP=new char*[L[i].somay];
        L[i].Sub=new char*[L[i].somay];
        for(int j = 0;j<L[i].somay;j++)
        {
            L[i].IP[j]=new char[100];
            L[i].Sub[j]=new char[100];
            cin>>L[i].IP[j]>>L[i].Sub[j];
        }
    }
    int dau, cuoi;
    cin>>dau>>cuoi;
    int d[91];
    int prev[91];
    int label[91];
    int kq=1;
    Dijkstra(L,d,prev,label,dau,cuoi,somang,kq);
    if(kq==0)
        return;
    cout<<"Yes\n";
    Show(dau,cuoi,prev);
}
void Init(int d[], int prev[], int label[], int n, int dau)
{
    for(int i=1; i<=n;i++)
    {
        d[i]=-1;
        prev[i]=-2;
        label[i]=1;
    }
    d[dau]=0;
}
void Dijkstra(LAN *L, int d[], int prev[], int label[], int dau, int cuoi, int somang,int &kq)
{
    Init(d,prev,label,somang,dau);
    while(label[cuoi]==1)
    {
        int iMin = -1;
        int v = -1;
        for(int i=1;i<=somang;i++)
        {
            if(label[i]==1 && d[i]!=-1&&(d[i]<iMin||iMin==-1))
            {
                iMin = d[i];
                v=i;
            }
        }
        if(iMin == -1)
        {
            cout<<"No";
            kq =0;
            break;
        }
        d[v]=iMin;
        label[v]=0;
        for(int j=1;j<=somang;j++)
        {
            if(label[j]==1&& ChungMang(v,j,L)==1)
            {
                d[j]=d[v]+1;
                prev[j]=v;
            }
        }
    }
}
int Test(char *IP3, char *IP4, char *Sub3, char *Sub4)
{
    char *IP1 = IP3;
    char *IP2=IP4;
    char *Sub1= Sub3;
    char *Sub2=Sub4;
    int i=0;
    int nIP=0;
    int nSub=0;
    while(nIP!=3)
    {
        if(IP1[i]=='.')
            nIP++;
        i++;
    }
    nIP=i;
    i=0;
    while(nSub!=3)
    {
        if(Sub1[i]=='.')
            nSub++;
        i++;
    }
    nSub=i;
    IP1[nIP]='\0';
    IP2[nIP]='\0';
    Sub1[nSub]='\0';
    Sub2[nSub]='\0';
    if(strcmp(IP1,IP2)==0&&strcmp(Sub1,Sub2)==0)
        return 1;
    return 0;
}

int ChungMang(int a, int b, LAN *L)
{
    int giong=0;
    for(int i=0;i<L[a].somay;i++)
    {
        for(int j = 0;j<L[b].somay;j++)
        {
            if(Test(L[a].IP[i],L[b].IP[j],L[a].Sub[i],L[b].Sub[j]))
                return 1;
        }
    }
    return 0;
}
void Show(int dau, int cuoi, int prev[])
{
    int temp[100];
    int i=99;
    int k = cuoi;
    cout<<dau;
    while (k != dau)
    {
        temp[i]=k;
        k=prev[k];
        i--;
    }
    for(int j = i+1;j<100;j++)
    {

            cout<<" "<<temp[j];
        cout<<endl;
    }
}