Pages

রবিবার, ২৯ ডিসেম্বর, ২০১৩

Solution code of uva 383

Problem link:383(Shipping routes)

Solution code:
           
 #include<cstdio>
#include<iostream>
#include<cstring>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<string>
using namespace std;
string source,destination;
vector<int>graph[33];
int calling_bfs(int s,int d)
{
   int visit[35];

    memset(visit,0,sizeof visit);
    queue<int>q;
    q.push(s);
    visit[s]=1;
  while(!q.empty())
  {
     int pop=q.front();q.pop();
     if(pop==d)
        return visit[d];
     for(int i=0;i<graph[pop].size();i++)
     {
        int v=graph[pop][i];
        if(visit[v]==0)
        {
          visit[v]=1+visit[pop];
          q.push(v);
        }
     }
  }
  return 0;
}
int main()
{
    //freopen("c:\\temp\\in.txt","r",stdin);
 int data_set;
 scanf("%d",&data_set);
   printf("SHIPPING ROUTES OUTPUT\n\n");
    for(int i=1;i<=data_set;i++)
    {
        if(i>1)printf("\n");
     int m,n,p;
     scanf("%d %d %d",&m,&n,&p);
      map<string,int>my;
      string node,u,v;
      for(int j=1;j<=m;j++)
      {
       cin>>node;
       my[node]=j;
      }
     for(int k=1;k<=n;k++)
     {
       cin>>u>>v;
       graph[my[u]].push_back(my[v]);
       graph[my[v]].push_back(my[u]);

     }
     int ship_size;

     printf("DATA SET  %d\n\n",i);
     for(int l=1;l<=p;l++)
     {
       scanf("%d",&ship_size);
       cin>>source>>destination;
       if(n==0)
        printf("NO SHIPMENT POSSIBLE\n");
       else
       {
         int legs=calling_bfs(my[source],my[destination]);
         if(legs==0) printf("NO SHIPMENT POSSIBLE\n");
         else printf("$%d\n",(legs-1)*100*ship_size);
       }
     }
      for(int i=1;i<=30;i++)
        graph[i].clear();
    }
    printf("\nEND OF OUTPUT\n");
     return 0;
}

0 comments:

একটি মন্তব্য পোস্ট করুন