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:
একটি মন্তব্য পোস্ট করুন