UVA 383 - Shipping Routes analysis

Problem Type : Single-Source Shortest Paths On Unweighted Graph  (BFS/DFS)

Its a basic SSSP problem.

"The cost of a shipment is equal to the size of the shipment times the number of shipping legs required times $100."

we just have to do a bfs or dfs from given source if we have't done bfs or dfs on the source before.We can get the cost of the shipment using the above statement using the cost of the destination :D

	#include<bits/stdc++.h>
	using namespace std;
	int mq,n,p;
	map<string,int>m;
	vector<int>v[35];
	int cost[35][35];
	bool dfsdone[35];
	void dfs(int z,int x){
	for(int i=0;i<v[x].size();i++){
	int xx = v[x][i];
	if(cost[z][x]+1<cost[z][xx]){
	cost[z][xx] = cost[z][x]+1;
	dfs(z,xx);
	}
	}
	}
	int main(){
	int t;
	string a,b;
	cin>>t;
	printf("SHIPPING ROUTES OUTPUT\n\n");
	for(int q=1;q<=t;q++){
	cin>>mq>>n>>p;
	memset(dfsdone,false,sizeof(dfsdone));
	for(int i=1;i<=mq;i++){
	cin>>a;
	m[a]=i;
	}
	for(int i=0;i<n;i++){
	cin>>a>>b;
	v[m[a]].push_back(m[b]);
	v[m[b]].push_back(m[a]);
	}
	printf("DATA SET %d\n\n",q);
	while(p--){
	int k;
	cin>>k>>a>>b;
	int aa = m[a],bb = m[b];
	if(dfsdone[aa]==false){
	for(int i=0;i<35;i++){
	cost[aa][i]=INT_MAX/3;
	}
	cost[aa][aa]=0;
	dfs(aa,aa);
	}
	if(cost[aa][bb]==INT_MAX/3){
	printf("NO SHIPMENT POSSIBLE\n");
	}
	else{
	int cos = k * cost[aa][bb]*100;
	printf("$%d\n",cos);
	}
	}
	for(int i=0;i<=mq;i++){
	v[i].clear();
	}
	cout<<"\n";
	}
	printf("END OF OUTPUT\n");
	}

view raw 383 - Shipping Routes.cpp hosted with ❤ by GitHub