## 10436 - Cheapest way

Moderator: Board moderators

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

### 10436 - Cheapest way

I notice that very few people solved this problem in the contest, is there something in which is not particularly well explained or understood ? Or is there an accuracy problem when solving it with the cost calculation ?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
There was a accuracy problem in the contest (some result was x.xx5 and in the judge output was x.xx). I know this because I asked the problemsetter.
But it is fixed now.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Ya, my WA during the contest got an AC on the first round. It's a textbook problem..

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
I spoke to Suman, and he sent this:

Dear Caesum,
The couple of solutions that I used to generate and check the problem all produced same result. Moreover while checking manually I found everything right. But now with your solution I got the BUG in the input which have a same little alternative path. I have corrected the input. Sorry for your pain that you may have undergone with this bug. I can't tell you when this fix will be available to judge, because I am also anxious about 10429 and 10435. I wish to update all together (if any) when they are ready.

However, One thing I must say your program does not produce unique path if destination is reversed. That is

path for (station1 station2) != reverse of path for (station2 station1)

Although it is ok for unique path.

Thanks for informing me the bug. Bye.

- Suman

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:   Code: Select all

``````#include<stdio.h>
#include<string.h>
#define INF 200
#define N 20
int p[N][N],c[N][N],b[N],n,l,d[N];
char a[N];
void init()
{
int i,j;
for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=INF,p[i][j]=i;
for(i=0;i<n;i++) c[i][i]=0;
}
void fw()
{
int k,j,i;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if((i!=k) && (j!=k) && (i!=j) && (c[i][k]+c[k][j]-b[k]>0) && (c[i][k]+c[k][j]-b[k])<c[i][j])
{
c[i][j]=c[k][j]+c[i][k]-b[k];
p[i][j]=k;
}
}
void print(int i,int j)
{
if(i!=j)
print(i,p[i][j]);
d[l++]=j;
}
main()
{
freopen("in.txt","r",stdin);
int cas,z,i,j,val,k,m,h;
char s,r;
double g;
scanf("%d",&cas);
for(z=0;z<cas;z++)
{
if(z) printf("\n");
printf("Map #%d\n",z+1);
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%s%d",a[i],&b[i]);
init();
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%s%s%d",s,r,&val);
for(j=0;j<n;j++) if(strcmp(a[j],s)==0) break;
for(k=0;k<n;k++) if(strcmp(a[k],r)==0) break;
c[j][k]=c[k][j]=2*val+b[k]+b[j];
}
fw();
scanf("%d",&m);
for(i=0;i<m;i++)
{
printf("Query #%d\n",i+1);
scanf("%s%s%d",s,r,&val);
for(j=0;j<n;j++) if(strcmp(a[j],s)==0) break;
for(k=0;k<n;k++) if(strcmp(a[k],r)==0) break;
l=0;
print(k,j);
for(h=0;h<l;h++)
{
if(h) printf(" ");
printf("%s",a[d[h]]);
}
g=c[k][j];
g+=g*.1;
g/=val;
printf("\nEach passenger has to pay : %.2lf taka\n",g);
}
}
return 0;
}
``````
it gets wa.
but i think there is no bug in the soln.
is there any critical input???
thanks..
waiting for bos's rply.
[/b]
"Everything should be made simple, but not always simpler"

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

### Tricky input

What about case when r and s are the same stations (find cheapest path from node to itself)? Your program outputs 0, instead of 1.1 * b[j] / val ?
Am I right? I think this is the only mistake you've made.

Maxim

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
but after modification why this is giving wa again??
i found no prob now.

Code: Select all

``````#include<stdio.h>
#include<string.h>
#define INF 200
#define N 20
int p[N][N],c[N][N],b[N],n,l,d[N];
char a[N];
void init()
{
int i,j;
for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=INF,p[i][j]=i;
for(i=0;i<n;i++) c[i][i]=0;
}
void fw()
{
int k,j,i;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if((i!=k) && (j!=k) && (i!=j) && (c[i][k]+c[k][j]-b[k]>0) && (c[i][k]+c[k][j]-b[k])<c[i][j])
{
c[i][j]=c[k][j]+c[i][k]-b[k];
p[i][j]=k;
}
}
void print(int i,int j)
{
if(i!=j)
print(i,p[i][j]);
d[l++]=j;
}
main()
{
freopen("in.txt","r",stdin);
int cas,z,i,j,val,k,m,h;
char s,r;
double g;
scanf("%d",&cas);
for(z=0;z<cas;z++)
{
if(z) printf("\n");
printf("Map #%d\n",z+1);
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%s%d",a[i],&b[i]);
init();
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%s%s%d",s,r,&val);
for(j=0;j<n;j++) if(strcmp(a[j],s)==0) break;
for(k=0;k<n;k++) if(strcmp(a[k],r)==0) break;
c[j][k]=c[k][j]=2*val+b[k]+b[j];
}
fw();
scanf("%d",&m);
for(i=0;i<m;i++)
{
printf("Query #%d\n",i+1);
scanf("%s%s%d",s,r,&val);
for(j=0;j<n;j++) if(strcmp(a[j],s)==0) break;
for(k=0;k<n;k++) if(strcmp(a[k],r)==0) break;
if(j==k)
{
printf("%s",s);
g=b[k];
g+=g*.1;
g/=val;
printf("\nEach passenger has to pay : %.2lf taka\n",g);
continue;
}
l=0;
print(k,j);
for(h=0;h<l;h++)
{
if(h) printf(" ");
printf("%s",a[d[h]]);
}
g=c[k][j];
g+=g*.1;
g/=val;
printf("\nEach passenger has to pay : %.2lf taka\n",g);
}
}
return 0;
}
``````
thanks again.  [/b]
"Everything should be made simple, but not always simpler"

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

### Don't know why

It's quite tricky to solve this problem using Floyd-Warshall. Your program doesn't work well because of additional cost when passing through some station. I've been testing your program and I couldn

rasel04
New poster
Posts: 9
Joined: Sun Dec 07, 2003 4:52 am

### 10436 - Cheapest Way - WA

I solved it using Dijkstra algorithm. But always got WA. Can some body check it or can give some critical input data?

Code: Select all

``````#include <stdio.h>
#include<string.h>
#define inf 1000000000.00
#define nIL -1
#define MAX 101

int g[MAX][MAX],p[MAX],deg[MAX];
bool taken[MAX];
int path[MAX];
int n,len;
char ch;
double cost[MAX][MAX],d[MAX],value[MAX];

void initSingleSource(int s)
{
int v;
for(v=1;v<=n;v++)
{
d[v]=inf;
p[v]=nIL;
taken[v]=false;
}
d[s]=0;
}
void relax(int u,int v)
{
if(d[v]>d[u]+value[u]+cost[u][v])
{
d[v]=d[u]+value[u]+cost[u][v];
p[v]=u;
}
}

int extraceMin(int s)
{
int i,u;
double minDist;
minDist=inf;
u=s;
for(i=1;i<=n;i++)
{
if(taken[i]==false && minDist>d[i])
{
minDist=d[i];
u=i;
}
}
return u;
}

void dijkstra(int s)
{
int u,i,v;
initSingleSource(s);
while(1)
{
u=extraceMin(s);
if(taken[u]==true)break;
taken[u]=true;
for(i=0;i<deg[u];i++)
{
v=g[u][i];
relax(u,v);
}
}
}

void findPath(int start,int end)
{
if ((start == end) || (end == nIL))
{
//printf("%d",start);
path[len++]=start;
}
else
{
findPath(start,p[end]);
path[len++]=end;
//printf(" %d",end);
}
}

void init()
{
int i;
for(i=0;i<=n;i++)
{
deg[i]=0;
}
}

int find(char str[])
{
int i;
for(i=1;i<=n;i++)
if(strcmp(ch[i],str)==0)
return i;
return 0;
}

void main()
{

int map=1,testcase,i,j,u,v,E,q,pass,que;
double ave,profit,total,c;
char str,str1,str2;
//freopen("10436.in","r",stdin);
scanf("%d\n",&testcase);
while(testcase--)
{
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
scanf("%s%lf\n",str,&c);
value[i]=c;
strcpy(ch[i],str);
}
scanf("%d\n",&E);
for(i=1;i<=E;i++)
{
scanf("%s%s%lf\n",str1,str2,&c);
u=find(str1);
v=find(str2);
g[u][deg[u]++]=v;
cost[u][v]=2.0*c;
}
scanf("%d\n",&q);
printf("Map #%d\n",map++);
que=1;
for(i=1;i<=q;i++)
{
printf("Query #%d\n",que++);
scanf("%s%s%d\n",str1,str2,&pass);
u=find(str1);
v=find(str2);
dijkstra(u);
len=1;
findPath(u,v);
total=value[v];
for(j=1;j<len-1;j++)
{
printf("%s ",ch[path[j]]);
}
total+=d[v];
printf("%s\n",ch[path[j]]);

profit=(total*0.100);
total+=profit;
ave=total/pass;
printf("Each passenger has to pay : %.2lf taka\n",ave);
}
printf("\n");

}
}

``````

Johnny_T
New poster
Posts: 2
Joined: Fri Sep 27, 2002 2:30 am

### Input problem

Hi!

I'm trying to solve this problem using Java, but I'm getting WA... which I then traced to a NumberFormatException thrown when reading the judge's input! Is there anything odd with the input that I'm missing? I couldn't find the bug during any of my tests... :\ I also noticed that there isn't any accepted Java submission for this problem! Probably because the Java support isn't very useful... :|
I'm not very experienced in Java submissions, can anyone help me pointing out some input parsing problems?

Here is my code for reading the input:
[java]

import java.util.* ;

class Main {
public static void main(String[] args) throws Exception {
try {
Moutushi m = new Moutushi() ;
m.Solve() ;
}
catch( NumberFormatException e) { while(true) ; }
}
}

class Moutushi {

Moutushi() throws Exception {
}

private int ReadInt() throws Exception {
if((stokenizer == null) || (!stokenizer.hasMoreTokens()))
do
while(!stokenizer.hasMoreTokens()) ;

return Integer.parseInt(stokenizer.nextToken()) ;
}

private double ReadDouble() throws Exception {
if((stokenizer == null) || (!stokenizer.hasMoreTokens()))
do
while(!stokenizer.hasMoreTokens()) ;

return new Double(stokenizer.nextToken()).doubleValue() ;
}

private String ReadString() throws Exception {
String tmp = new String() ;
if((stokenizer == null) || (!stokenizer.hasMoreTokens()))
do
while(!stokenizer.hasMoreTokens()) ;

return stokenizer.nextToken() ;
}

// copied from another post on this forum

/* read token from stdIn with custom delims */
/* returns null for end of file or any exceptions */
static String token( String delim ){
char c = delim.charAt(0);
StringBuffer s = new StringBuffer("");
try{
while( delim.indexOf( (int) c ) != -1 && c != 65535 )
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}
// end of copy

private void GetProblemData() throws Exception {
vertexes = new Hashtable( 2 * vertexcount ) ;
vertexnames = new Vector(vertexcount) ;
unused = new PriorityQueue(vertexcount) ;

String name ;
for(int i = 0 ; i < vertexcount ; i++) {
}

Vertex v1, v2 ;
double cost ;
for(int i = 0 ; i < connectioncount ; i++) {
cost = 2 * ReadDouble() ;

}

}

public void Solve() throws Exception {
for(int i = 1 ; i <= mapcount ; i++) {
GetProblemData() ;
System.out.println("Map #" + i) ;
for(int k = 1 ; k <= querycount ; k++) {
InitQueue() ;
if(!origin.equals(objective))
ComputeMinCosts() ;
System.out.println("Query #" + k) ;
}
if(i != mapcount)
System.out.println() ;
}
}

[/java]

rasel04
New poster
Posts: 9
Joined: Sun Dec 07, 2003 4:52 am

### WA-10436

Is there not any body who can see my code and find the mistakes ? I think my whole method is OK. But there can be some precision error. So I am getting WA. Please check my code and find mistakes. Thanks in advance.
[/b]

jackie
New poster
Posts: 47
Joined: Tue May 04, 2004 4:24 am
The problem setter said:
It is guaranteed that each map description is valid, and the query has a valid and unique path.
But i don't think it's correct after many WAs and finaly AC.

The trouble is "unique path". If you use differnt algorithm. it may generate different path and the passenger cost is same.

You'd better use Dijkstra algorithm it can generate same path as the judge's output for now.

In all the problem should be specially judged or the input data shoulbe be changed!

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm
helo Jackie!

Did you verified your assumptions or simply changed from non-Dijkstra
to Dijkstra? I just tested the input of uva/10436 and found that you are
right because there is a map with a query such that a source has at least two
min cost path to some(!) node, but not to target node, so you are wrong too.

good luck,
csaba noszaly

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

### 10436. --Though quite easy, but gettin RTE

Hi all,

I've tried 2 solve this prob using bellman-ford. And also tested it with several inputs. But the OJ is giving RTE. Can some1 help me? I'm giving the code.

Code: Select all

``````#include<cstdio>
#include<stack>
#include<cstring>

using namespace std;

#define INF 9999999

typedef struct Node{
char name;
} Node;

typedef struct Edge{
char u,v;
int s,e;
int w;
} Edge;

void main(){
int v,E,i,j,k,m,caseno,p,q,ss,dd;
int pre,d,cost;
char so,des;
Node node;
Edge edge;
stack<int> S;

//	freopen("C:\\4.txt","r",stdin);

scanf("%d",&caseno);

for(int count=1;count<=caseno;count++){

printf("Map #%d\n",count);

scanf("%d",&v);
getchar();
for(i=0;i<v;i++){
scanf("%s %d",&node[i].name,&cost[i]);
getchar();
}

scanf("%d",&E);
E*=2;
for(i=0;i<E;i+=2){
scanf("%s %s %d",&edge[i].u,&edge[i].v,&edge[i].w);
edge[i].w*=2;
getchar();
strcpy(edge[i+1].v,edge[i].u);
strcpy(edge[i+1].u,edge[i].v);
edge[i+1].w=edge[i].w;
}

for(i=0;i<E;i++){
for(j=0;j<v;j++){
if(!strcmp(edge[i].u,node[j].name)) edge[i].s=j;
if(!strcmp(edge[i].v,node[j].name)) edge[i].e=j;
}
}

scanf("%d",&q);
for(k=1;k<=q;k++){
printf("Query #%d\n",k);
scanf("%s %s %d",&so,&des,&p);
for(i=0;i<v;i++) {
if(!strcmp(so,node[i].name)) ss=i;
if(!strcmp(des,node[i].name)) dd=i;
}

for(i=0;i<v;i++){
d[i]=INF;
pre[i]=0;
}

d[ss]=0;

for(i=0;i<v-1;i++){
for(j=0;j<E;j++){
if(d[edge[j].e]>d[edge[j].s]+edge[j].w+cost[edge[j].s]){
d[edge[j].e]=d[edge[j].s]+edge[j].w+cost[edge[j].s];
pre[edge[j].e]=edge[j].s;
}
}
}

d[dd]+=cost[dd];
double t_cost=d[dd]+0.1*d[dd];
double fare=t_cost/(double) p;

while(!S.empty()) S.pop();
S.push(dd);
m=dd;
while(m!=ss){
m=pre[m];
S.push(m);
}

i=0;
while(!S.empty()){
i++;
if(i==1){
printf("%s",node[S.top()].name);
S.pop();
}
else{
printf(" %s",node[S.top()].name);
S.pop();
}
}

putchar('\n');
printf("Each passenger has to pay : %.2lf taka\n",fare);
}
putchar('\n');
}
}
``````
-Shihab
Shihab
CSE,BUET

hekacyr
New poster
Posts: 7
Joined: Sat Oct 19, 2002 1:25 pm

### ambigous inputs

i verified that there are ambigous inputs. this is part of my code which gives AC whithout the check and RE whith the for loop to check for ambigous paths. (the for loop checks, while doing the output, if there is an edge not going to the parent wich would give the same distance to the start node)

Code: Select all

``````
while (parent[curr] != -1) {
// check for buggy inputs
for (list<pair<int,double> >::const_iterator it = towns[curr].edges.begin();
it != towns[curr].edges.end(); ++it) {
if (it->first != parent[curr] &&
distances[it->first] + it->second ==  distances[curr]) {
abort();
}
}
curr = parent[curr];
cout << " " << town_names[curr];
}
``````
so it would be nice, if the judge input could be corrected. thx
-j