UVA- 567 : Risk

//Problem  link >>http://uva.onlinejudge.org/external/5/567.html

Graph  problem  using  floyd-warshall ...

#include <bits/stdc++.h>
#define  inf  100000
using namespace std ;

int con[24][24] ;

int main ()
{
    int n ,cas=1 , line ,m ;
    while ( cin>>n && n!=EOF )
    {
        int i , j ;
        for (i=0; i<=20 ; i++)
        {
            for (j=0; j<=20 ; j++)
            {
                if (i==j) con[i][j]=0 ;
                else con[i][j]=inf ;
            }
        }

            line=1 ;
            for (int i=1 ; i<=n ; i++)
            {
                  cin>>m ;
                 con[m][line]=con[line][m]=1 ;

            }
          line++ ;

        while (line<20)
        {
            cin>>n ;
            for (int j=1 ; j<=n ; j++)
            {
                int m ;
                cin>>m ;
                con[m][line]=con[line][m]=1 ;

            }
             line++ ;
        }

        int q , k ;
        for (k=1 ; k<=20 ; k++)
        {
             for (i=1; i<=20 ; i++)
            {
               for (j=1 ; j<=20 ; j++)
                {
                    con[i][j]=min(con[i][j],con[i][k]+con[k][j]) ;
                }
            }
        }

        cin>>q ;
        cout<<"Test Set #"<<cas++<<endl ;

        for (i=1 ; i<=q ; i++)
        {
            int a , b ;
            cin>>a>>b ;
              printf ("%2d to %2d: %d\n",a,b,con[a][b]) ;

        }
        cout<<endl ;

    }

    return 0 ;
}

UVA- 10171 >> Meeting Prof. Miguel

// Problem  link >>http://uva.onlinejudge.org/external/101/10171.html

... Graph problem  ...  u  have to  use  Floyd-warshall  algo ...

#include <bits/stdc++.h>
#define inf 100000
using namespace std ;

int main ()
{
    int n , i ;
    while (cin>>n && n!=0)
    {

            int ar1[150][150] ;
            int ar2[150][150] ;

            for (int i='A' ; i<='Z' ; i++)
            {
                for (int j='A' ; j<='Z' ; j++)
                {
                    if (i==j)
                    {
                        ar1[i][j]=0 ;
                        ar2[i][j]=0 ;
                    }
                    else
                    {
                        ar1[i][j]=inf ;
                        ar2[i][j]=inf ;
                    }
                }
            }

        while (n--)
        {
            char c1 ,c2 , c3 , c4 ;
            int x ;

          cin>>c1>>c2>>c3>>c4>>x ;

           if (c1=='Y')
            {
                if (c2=='U') ar1[c3][c4]=min (x,ar1[c3][c4]) ;
                else
                {
                    ar1[c3][c4]=min(x,ar1[c3][c4]) ;
                    ar1[c4][c3]=min(x,ar1[c4][c3]) ;
                }
            }

         else if (c1=='M')
         {
             if (c2=='U') ar2[c3][c4]=min(x,ar2[c3][c4]) ;
             else
             {
                 ar2[c3][c4]=min(x,ar2[c3][c4]) ;
                 ar2[c4][c3]=min(x,ar2[c4][c3]);
             }
         }

        }

///////////////////////////// // floyd  warshalll
        for (int k='A' ; k<='Z' ; k++)
         {
              for (int i='A' ; i<='Z' ; i++)
             {
                 for (int j='A' ; j<='Z' ; j++)
                 {
                     ar1[i][j]=min(ar1[i][j],ar1[i][k]+ar1[k][j]) ;
                     ar2[i][j]=min(ar2[i][j],ar2[i][k]+ar2[k][j]) ;
                 }
             }
         }

            vector<int>v ;
         char a , b ;
         cin>>a>>b ;
       int mn=inf  ;
       v.clear() ;

       for (int i='A' ; i<='Z' ; i++)
       {
           if (ar1[a][i]+ar2[b][i]<mn)
           {
               v.clear() ;
               v.push_back(i) ;
               mn=ar1[a][i]+ar2[b][i] ;
           }
           else if (mn==ar1[a][i]+ar2[b][i]) v.push_back(i) ;

       }

       if (mn==inf) cout<<"You will never meet."<<endl ;
        else
        {
            sort(v.begin() , v.end()) ;
            cout<<mn ;
            int sz=v.size();
             for (int i=0; i<sz ; i++)
             {
                     printf(" %c",v[i]);
            }
             cout<<endl ;
        }

    }

    return 0 ;
}

some  critical  case ::::
3
Y U X Y 5
M B A Y 10
Y B X Y 10
X A
AC  output : 15 Y

2
Y U B D 0
M U B D 0
B B
AC  output : 0 B D

2
Y U X Z 1
Y U X Z 10
X Z
AC  output : 1 Z