## 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

Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:
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
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 :(

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

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

### Re: 10436 - Cheapest Way

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...............................