ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1072. Routing

[Help me] What is Test#3
Posted by [LTDT02]1112477 27 Nov 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;
    }
}