10436 - Cheapest way

[Caesum]

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 ?

[Adrian Kuegel]

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]

Ya, my WA during the contest got an AC on the first round. It's a textbook problem..

[Caesum]

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]

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][50];
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[50],r[50];
	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;
}

please any1 help.
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]

[Maxim]

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]

thanks for your great help.
but after modification why this is giving wa again??
please check.
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][50]; 
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[50],r[50]; 
   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]

[Maxim]

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]

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[100][100];
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[100],str1[100],str2[100];
	//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]

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 {
mapcount = ReadInt() ;
}

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

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

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

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

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

return stokenizer.nextToken() ;
}

// copied from another post on this forum
static String readLine(){return token( "\n\r" ); }

/* 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 )
c = (char) System.in.read();
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){
s.append( (char) c );
c = (char) System.in.read();
}
}catch( Exception e ){ return (null); }
if( s.toString().equals("") ) return null;
return s.toString();
}
// end of copy

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

String name ;
for(int i = 0 ; i < vertexcount ; i++) {
vertexes.put(name = ReadString(), new Vertex(name, ReadDouble(), i)) ;
vertexnames.addElement((Object)name) ;
}

connectioncount = ReadInt() ;

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

v1.connections.addElement(new Connection(v2.getIndex(), cost)) ;
v2.connections.addElement(new Connection(v1.getIndex(), cost)) ;
}

querycount = ReadInt() ;
}

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++) {
origin = ((Vertex)vertexes.get(ReadString())) ;
objective = ((Vertex)vertexes.get(ReadString())) ;
InitQueue() ;
if(!origin.equals(objective))
ComputeMinCosts() ;
System.out.println("Query #" + k) ;
DisplayMinPath(ReadInt()) ;
}
if(i != mapcount)
System.out.println() ;
}
}

[/java]

[rasel04]

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]

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]

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]

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[50];
} Node;

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

void main(){
	int v,E,i,j,k,m,caseno,p,q,ss,dd;
	int pre[30],d[30],cost[30];
	char so[50],des[50];
	Node node[30];
	Edge edge[30];
	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

[hekacyr]

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