10436 - Cheapest way

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Post by Carlos » Sat Nov 25, 2006 5:17 pm

judge's input has been slightly modified to avoid multiple minimum cost paths.
DON'T PM ME --> For any doubt, suggestion or error reporting, please use the "Contact us" form in the web.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Sat Oct 13, 2007 9:55 pm

Correct output for this:

Code: Select all

1

1
limpopo 1
0
1
limpopo limpopo 1
?
EDIT: Pretty sure the solution is ok, but still WA.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

zooom
New poster
Posts: 4
Joined: Tue Jun 12, 2007 9:20 am

TLE !!! SOS for HELP :(

Post by zooom » Sat Nov 17, 2007 5:06 pm

My Solution gives TLE :( :( for n=20 its looks quite impossible .. Can someone Tell me the reason for this strange behavior .. I use Dijkstra's to find the shortest path .. here's my code..

Code: Select all

#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<vector>
#include<stdio.h>
using namespace std;
bool dijkstra(vector< vector<int> >a,int source,int dest,int n,int pass,map<string,int>b,map<string,int>c,vector<string>names);
int main(){
int testcases;
cin>>testcases;
int maps=1;
bool anand=false;
while(testcases>0){
if(anand){
cout<<endl;
}
anand=true;
int n;
cin>>n;
vector< vector<int> >a(n,vector<int>(n));
map<string,int>c;
map<string,int>b;
int count=0;
vector<string>names;
	for(int i=0;i<n;i++){
		string s;
		int t;
		cin>>s>>t;
		names.push_back(s);
		c[s]=t;
		b[s]=count;
		count++;
	}
int rules;
cin>>rules;
	for(int i=0;i<rules;i++){
		string s1,s2;
		cin>>s1>>s2;
		int temp;
		cin>>temp;
		a[b[s1]][b[s2]]=temp;
	}
int query;
cin>>query;
cout<<"Map #"<<maps<<endl;
	for(int i=0;i<query;i++){
		string s1,s2;
		int pass;
		cin>>s1>>s2>>pass;
		cout<<"Query #"<<i+1<<endl;
		dijkstra(a,b[s1],b[s2],n,pass,b,c,names);
	}
maps++;
testcases--;
}
}

bool dijkstra(vector< vector<int> >a,int source,int dest,int n,int pass,map<string,int>b,map<string,int>c,vector<string>names){
vector<int>d(n,INT_MAX);
int destn=dest;
d[source]=0;
map<int,int>p;
p[source]=-1;
vector<bool>found(n);
int count=0;
		while(1){
			if(count==n){
			break;
			}
			bool founder=false;
			int temp=0;
			int minm=INT_MAX;
				for(int i=0;i<d.size();i++){
					if(d[i]<minm && !found[i]){
						temp=i;
						minm=d[i];
						founder=true;
					}
				}
			if(!founder){
			break;
			}
			for(int i=0;i<n;i++){
				if(a[temp][i]!=0 && d[temp]!=INT_MAX){
					if(d[i]>d[temp]+a[temp][i]){
						d[i]=d[temp]+a[temp][i];
						p[i]=temp;
						}
				}
			}
		count++;
		found[temp]=1;
		}
double km=0.0;
km+=(2.0*d[dest]);
km+=c[names[dest]];
vector<string>ans;
ans.push_back(names[dest]);
		while(p[dest]!=-1){
			int ter=p[dest];
			dest=ter;
			ans.push_back(names[ter]);
			km+=(c[names[ter]]);
		}
		for(int i=ans.size()-1;i>=1;i--){
			cout<<ans[i]<<" ";
		}
	if(source==destn){
		cout<<names[source]<<" ";
	}
cout<<ans[0]<<endl;
km+=(0.10*km);
km=km/(double)pass;
cout<<"Each passenger has to pay : ";
printf ("%4.2f",km);
cout<<" taka"<<endl;
}
Please Tell .. I am Fed up :(

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10436 - Cheapest Way

Post by kbr_iut » Fri Sep 12, 2008 1:24 am

problem says that
Next `nPath' contains ``station1 station2 distance'', describing `station1' has a path to `station2' with distance equal to `distance' in kilometer and vice versa.
that means the edges are bidirectional which is not handled in ur code.
ur code gives TLE for this input

Code: Select all

1

2
ab 1
ba 1
1
ab ba 1
1
ba ab 1
and about blank line there is no hints in problem.The problem should contain this line
print a blank line between the output of each map.
however this problem can simply be solved with floyed warshall.
hope it will help.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Post Reply

Return to “Volume 104 (10400-10499)”