Light OJ: 1055 – Going Together

Problem Link : http://lightoj.com:81/volume/problem/1055


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
const int fx[]= {+1,-1,+0,+0};
const int fy[]= {+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/


struct data
{
    pii a,b,c;
};

string graph[15];
map<pii,bool>mp;
int n;

bool vis[10][10][10][10][10][10];
int dis[10][10][10][10][10][10];

bool check(pii aa)
{
    if(aa.ff>=0 && aa.ff<n && aa.ss>=0 && aa.ss<n && graph[aa.ff][aa.ss]!='#')
        return 1;
    return 0;
}


int bfs(data src)
{
    vis[src.a.ff][src.a.ss][src.b.ff][src.b.ss][src.c.ff][src.c.ss]=1;
    dis[src.a.ff][src.a.ss][src.b.ff][src.b.ss][src.c.ff][src.c.ss]=0;
    queue<data>Q;
    Q.push(src);
    while(!Q.empty())
    {
        data u=Q.front();
        Q.pop();
        if(mp[u.a] && mp[u.b] && mp[u.c] && u.a!=u.b && u.a!=u.c && u.b!=u.c)
        {

            return dis[u.a.ff][u.a.ss][u.b.ff][u.b.ss][u.c.ff][u.c.ss];
        }
        for(int i=0; i<4; i++)
        {
            data v;
            pii aa=pii(u.a.ff+fx[i],u.a.ss+fy[i]);
            if(!check(aa)) aa=u.a;
            pii bb=pii(u.b.ff+fx[i],u.b.ss+fy[i]);
            if(!check(bb)) bb=u.b;
            pii cc=pii(u.c.ff+fx[i],u.c.ss+fy[i]);
            if(!check(cc)) cc=u.c;

            if(aa==bb)
            {
                if(bb==cc)
                    cc=u.c;
                aa=u.a;
                bb=u.b;
            }
            if(aa==cc)
            {
                aa=u.a;
                cc=u.c;
            }
            if(bb==cc)
            {
                bb=u.b;
                cc=u.c;
                if(bb==aa)
                    aa=u.a;
            }

            v.a=aa;
            v.b=bb;
            v.c=cc;
            if(vis[v.a.ff][v.a.ss][v.b.ff][v.b.ss][v.c.ff][v.c.ss]==0)
            {
                vis[v.a.ff][v.a.ss][v.b.ff][v.b.ss][v.c.ff][v.c.ss]=1;
                dis[v.a.ff][v.a.ss][v.b.ff][v.b.ss][v.c.ff][v.c.ss]=dis[u.a.ff][u.a.ss][u.b.ff][u.b.ss][u.c.ff][u.c.ss]+1;
                Q.push(v);
            }
        }

    }
    return -1;
}

int main()
{

    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    CIN;
    int t;
    cin>>t;
    TEST_CASE(t)
    {
        cin>>n;
        loop(i,n) cin>>graph[i];
        mp.clear();
        data src;
        loop(i,n) loop(j,n)
        {
            if(graph[i][j]=='X') mp[pii(i,j)]=1;
            if(graph[i][j]=='A') src.a=pii(i,j);
            if(graph[i][j]=='B') src.b=pii(i,j);
            if(graph[i][j]=='C') src.c=pii(i,j);
        }

        ms(vis,0);
        ms(dis,0);
        int ans=bfs(src);
        CASE_PRINT;
        if(ans==-1)
            cout<<"trapped"<<endl;
        else
            cout<<ans<<endl;
    }

    return 0;
}


Advertisements

ACM-ICPC Live Archive : 4109 – USHER

Problem Link : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2110


/*
     If opportunity doesn't knock, build a door.

            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |S|.|S|.|R|.|A|.|S|.|A|.|M|.|K|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    Success is how high you bounce when you hit bottom.
*/


#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              10000019
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

vector<int>graph[505],cost[505];
int cap,p,usernum;

int aa=INT_MAX;

int bfs(int src, int dst)
{
    int dis[505];
    for(int i=0;i<505;i++) dis[i]=infinity;
    dis[src]=0;
    queue<int>Q;
    Q.push(src);
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        for(int i=0;i<SZ(graph[u]);i++)
        {
            int v=graph[u][i];
            if(dis[u]+cost[u][i]<dis[v])
            {
                dis[v]=dis[u]+cost[u][i];
                Q.push(v);
            }
        }
    }
    return dis[dst];
}



int main()
{

//     freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);


    int t;
    while(sf(t)==1 && t)
    {
        TEST_CASE(t)
        {
//            D(z);
            for(int i=0;i<505;i++)
            {
                graph[i].clear();
                cost[i].clear();
            }
            sff(cap,p);
            vector<int>user;
            sf(usernum);
            loop(i,usernum)
            {
                int a;
                sf(a);
                user.pb(a);
            }

            for(int i=1;i<=p;i++)
            {
                int xx;
                sf(xx);
                for(int j=1;j<=xx;j++)
                {
                    int a,b;
                    sff(a,b);
                    graph[i].pb(b);
                    cost[i].pb(a);
                }
            }

            aa=INT_MAX;

            for(int i=0;i<SZ(user);i++)
            {
                aa=min(aa,bfs(user[i],0));
            }

            if(aa==0)
            {
                pf("0\n");
                continue;
            }

            {
                int sum=0;
                int ans=0;
                sum=0;
                while(sum<cap)
                {
                    sum+=(aa);
                    if(sum>=cap) break;
                    sum--;
                    ans++;
                }
                pf("%d\n",ans);
            }


        }
    }
    return 0;
}


BFS Sample Code


#include <bits/stdc++.h>

using namespace std;

vector<int>G[100]; // Here 100 is maximum number of Nodes.
bool visited[100];
int parent[100]; // This is used to print path from source to distance
int dis[100];
int node,edge;

void path_print(int u)
{
    if(u==-1) return;
    path_print(parent[u]);
    printf("%d ",u);
}

void bfs(int src)
{
    queue<int>Q;
    Q.push(src);
    dis[src]=0;
    parent[src]=-1;
    memset(visited,0,sizeof visited);
    visited[src]=1 ;

    while(!Q.empty())
    {
        int u=Q.front();
        for(int i=0; i<G[u].size(); i++)
        {
            int v=G[u][i];
            if(!visited[v])
            {
                dis[v]=dis[u]+1 ;
                parent[v]=u;
                visited[v]=1 ;
                Q.push(v);
            }
        }
        Q.pop();
    }
    for(int i=1 ; i<=node; i++)
    {
        printf("%d to %d distance = %d\n",src,i,dis[i]);
        printf("Path = ");
        if(visited[i])
        path_print(i);
        printf("\n");
    }
}

int main()
{
    cin>>node>>edge;
    for(int i=1; i<=edge; i++)
    {
        int a,b;
        cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int src;
    cin>>src;
    bfs(src);
    return 0;
}


UVa 762 – We Ship Cheap

Problem Link :https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=703

Solution Idea:

After reading the problem statement It’s clear that this is a shortest path problem and we can solve this using BFS. In this problem all the nodes are string. so we use map for mapping strings with integers and run a BFS.

The main problem is is problem is it’s test cases. This problem have a lots of critical case. Like source and destination is not present on the input graph and Source and Destination is the same node.

Think carefully about this test cases and handle them separately and Most important thing in solving graph problem is clearing the whole graph and arrays after each test cases.


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

vector<int>G[10005];
map<string,int>mp;
map<int,string>mp1;

int d[10005];
bool visit[10005];
int dir[10005];
int cnt=0;

int bfs(int src, int dst)
{
    queue<int>Q;
    d[src]=0;
    visit[src]=1;
    Q.push(src);
    dir[src]=src;
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        if(u==dst) return 1;

        loop(i,SZ(G[u]))
        {
            int v=G[u][i];
            if(!visit[v])
            {
                visit[v]=1;
                d[v]=d[u]+1;
                Q.push(v);
                dir[v]=u;
            }
        }
    }
    return -1;
}

void path_print(int a, int b)
{
   if(a==b) return;
   path_print(dir[a],b);
   cout<<mp1[dir[a]]<<" "<<mp1[a]<<endl;
}

void allclear(int n)
{
    loop(i,n)
    {
        G[i].clear();
        d[i]=visit[i]=dir[i]=0;
    }
    mp.clear();
    mp1.clear();
    cnt=0;
}

int main()
{
    CIN;
//    freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int n;
    bool test=0;
    while(cin>>n)
    {
        if(test) cout<<endl;
        test=1;
        string s1,s2;
        loop(i,n)
        {
            cin>>s1>>s2;
            if(mp[s1]==0)
               {
                 mp[s1]= ++cnt;
                 mp1[cnt]=s1;
               }
            if(mp[s2]==0)
                {
                    mp[s2]= ++cnt;
                    mp1[cnt]=s2;
                }
            G[mp[s1]].pb(mp[s2]);
            G[mp[s2]].pb(mp[s1]);
        }

        cin>>s1>>s2;
        if(s1==s2)
            cout<<s1<<" "<<s1<<endl;
        else if((mp[s1]==0 || mp[s2]==0))
        {
            cout<<"No route"<<endl;
        }
        else if(bfs(mp[s1],mp[s2])==-1)
            cout<<"No route"<<endl;
        else
            path_print(mp[s2],mp[s1]);

    allclear(cnt+5);

    }
    return 0;
}

USACO: Mother’s Milk

Problem Link : http://train.usaco.org/usacoprob2?a=tffkkLavmsp&S=milk3


/*
PROG: milk3
LANG: C++
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

/*-----------------------Bitmask------------------*/
//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct data
{
    int a,b,c;
    data()
    {
        ;
    }
    data(int x, int y, int z)
    {
        a=x,b=y,c=z;
    }
};

int A,B,C;

bool ans[30];

bool visited[30][30][30];
int first=100;

void BFS(data x)
{
    map<data,bool>mp;
    queue<data>Q;
    visited[x.a][x.b][x.c]=1;
    Q.push(x);
    while(!Q.empty())
    {
        data u=Q.front();
        Q.pop();
        if(u.a==0) ans[u.c]=1,first=min(first,u.c);
        int bb=B-u.b,aa=A-u.a,cc=C-u.c;
        if(u.c)
        {
            data c2b=u,c2a=u;
            if(bb>=u.c)
            {
                c2b.b+=u.c;
                c2b.c=0;
            }
            else if(bb<u.c)
            {
                c2b.b=B;
                c2b.c-=bb;
            }

            if(aa>=u.c)
            {
                c2a.a+=u.c;
                c2a.c=0;
            }
            else if(aa<u.c)
            {
                c2a.a=A;
                c2a.c-=aa;
            }
            if(!visited[c2b.a][c2b.b][c2b.c])
            {
                Q.push(c2b);
                visited[c2b.a][c2b.b][c2b.c]=1;
            }
            if(!visited[c2a.a][c2a.b][c2a.c])
            {
                Q.push(c2a);
                visited[c2b.a][c2b.b][c2b.c]=1;
            }
        }

        if(u.b)
        {
            data b2a=u,b2c=u;
            if(aa>=u.b)
            {
                b2a.a+=u.b;
                b2a.b=0;
            }
            else
            {
                b2a.a=A;
                b2a.b-=aa;
            }
            if(cc>=u.b)
            {
                b2c.c+=u.b;
                b2c.b=0;
            }
            else
            {
                b2c.c=C;
                b2c.b-=cc;
            }
            if(!visited[b2a.a][b2a.b][b2a.c])
            {
                visited[b2a.a][b2a.b][b2a.c]=1;
                Q.push(b2a);
            }
            if(!visited[b2c.a][b2c.b][b2c.c])
            {
                visited[b2c.a][b2c.b][b2c.c]=1;
                Q.push(b2c);
            }
        }

        if(u.a)
        {
            data a2b=u,a2c=u;
            if(bb>=u.a)
            {
                a2b.b+=u.a;
                a2b.a=0;
            }
            else
            {
                a2b.b=B;
                a2b.a-=bb;
            }
            if(cc>=u.a)
            {
                a2c.c+=u.a;
                a2c.a=0;
            }
            else
            {
                a2c.c=C;
                a2c.c-=cc;
            }
            if(!visited[a2c.a][a2c.b][a2c.c])
            {
                visited[a2c.a][a2c.b][a2c.c]=1;
                Q.push(a2c);
            }
            if(!visited[a2b.a][a2b.b][a2b.c])
            {
                visited[a2b.a][a2b.b][a2b.c]=1;
                Q.push(a2b);
            }
        }

    }
}

int main()
{
    freopen("milk3.in","r",stdin);
    freopen("milk3.out","w",stdout);
    cin>>A>>B>>C;
    BFS(data(0,0,C));

    cout<<first;
    for(int i=first+1; i<=C; i++) if(ans[i]) cout<<" "<<i;
    cout<<endl;
    return 0;
}


UVa 429 – Word Transformation


/*
User ID: turing_13
Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=370
*/

/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;


//map <string,int> mp;
map <string,bool> visited;
map <string,int> d;
map< string,vector<string> >graph;
string str1;
vector <string> v[15];

bool test(string s1,string s2)
{
    int cnt=0;
    loop(i,SZ(s1))
    {
        if(s1[i]!=s2[i])
            cnt++;
        if(cnt==2) return false;
    }
    return true;
}

int BFS(string str1, string str2)
{
    visited[str1]=1;
    queue<string>Q;
    d[str1]=0;
    Q.push(str1);
    while(!Q.empty())
    {
        string p=Q.front();
        Q.pop();
        if(p==str2) return d[str2];
        for(int i=0; i<SZ(graph[p]); i++)
        {
            string q=graph[p][i];
            if(visited[q]==0)
            {
                visited[q]=1;
                d[q]=d[p]+1;
                Q.push(q);
            }
        }
    }
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    char c;
    sf(t);
    while(t--)
    {
        while(cin>>str1 && str1!="*")
        {
            int x=SZ(str1);
            v[x].pb(str1);
            loop(i,SZ(v[x]))
            {
                string temp=v[x][i];
                if(test(str1,temp))
                {
                    graph[str1].pb(temp);
                    graph[temp].pb(str1);
                }
            }
        }
        getchar();
        string ss1,ss2,str2;
        while(1)
        {
            getline(cin,str2);
            if(str2=="") break;
            bool test=0;
            int xx=str2.size();
            loop(i,xx)
            {
                if(str2[i]==' ') {test=1;continue;}
                if(!test) ss1+=str2[i];
                else ss2+=str2[i];
            }
            int ans= BFS(ss1,ss2);
            cout<<ss1<<" "<<ss2<<" "<<ans<<endl;
            visited.clear();
            d.clear();
            ss1.clear();
            ss2.clear();
            str2.clear();
        }
        if(t)
            cout<<endl;
    }
    return 0;
}

Light OJ 1257 – Farthest Nodes in a Tree (II)

Problem Link : http://www.lightoj.com/volume_showproblem.php?problem=1257


/*
         +-+ +-+ +-+
         |R| |.| |S|
         +-+ +-+ +-+
 */

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             30001
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d:\n",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long


using namespace std;

vector<int> graph[MAX],cost[MAX];

int dis[MAX];
int dis1[MAX];
int a,b,max_dis,n;

void BFS(int src)
{
    dis[src]=0;
    queue<int>Q;
    Q.push(src);
    while(!Q.empty())
    {
        int u= Q.front();
        Q.pop();
        if(dis[u]>max_dis)
        {
            max_dis=dis[u];
            a=u;
        }
        loop(i,SZ(graph[u]))
        {
            int v=graph[u][i];
            if(dis[v]==-1)
            {
                dis[v]=dis[u]+cost[u][i];
                Q.push(v);
            }
        }
    }
}

void BFS1(int src)
{
    dis1[src]=0;
    queue<int>Q;
    Q.push(src);
    while(!Q.empty())
    {
        int u= Q.front();
        Q.pop();
        loop(i,SZ(graph[u]))
        {
            int v=graph[u][i];
            if(dis1[v]==-1)
            {
                dis1[v]=dis1[u]+cost[u][i];
                Q.push(v);
            }
        }
    }
}

void allclear()
{
    loop(i,n+1)
    {
        graph[i].clear();
        cost[i].clear();
        dis[i]=-1;
        dis1[i]=-1;
    }
    max_dis=-1;
    a=b=-1;
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t,x,y,w;
    sf(t);

    TEST_CASE(t)
    {
        sf(n);
        allclear();
        loop(i,n-1)
        {
            sfff(x,y,w);
            graph[x].pb(y);
            graph[y].pb(x);
            cost[x].pb(w);
            cost[y].pb(w);
        }
        BFS(0);
        b=a;
        loop(i,n+1)
            dis[i]=-1;
        max_dis=-1;
        BFS(b);
        b=a;
        BFS1(b);
        PRINT_CASE;
        loop(i,n)
        {
            pf("%d\n",max(dis[i],dis1[i]));
        }
    }
    return 0;
}

Algorithm:

1. Run a BFS from any node and determine the farthest node from it and Name this node as b.
2. Run another BFS from b and save all node’s distance from b (dis array). and determine the farthest node from b and name this node as a;
3. Run another BFS from a and save all nodes distance from a (dis1 array).
4. Now print for all node max(dis[node], dis1[node]).