10816 - Travel in Desert

All about problems in Volume 108. 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
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Feb 15, 2005 11:03 pm

I don't understand why you need 2 Dijkstra's. Why can't you just do 1 Dijkstra's where the depth[] of each vertex contains a pair (temp,length). Then when you relax edges, if
depth = (t1, s1)
and edge u->v has (t2, s2),
then you set
depth[v] = (max(t1,t2), s1 + s2)
This is like doing Prim's and Dijkstra's at the same time. Why is this wrong? I'm getting WA.
If only I had as much free time as I did in college...

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Feb 15, 2005 11:06 pm

Did you try the test case I posted?
Btw, you can also do it with only one dijkstra, but on a different graph (with (#different temperatures)*n nodes).
Last edited by Adrian Kuegel on Tue Feb 15, 2005 11:09 pm, edited 1 time in total.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Feb 15, 2005 11:08 pm

Yes, I get the right answer on all the posted test cases.
If only I had as much free time as I did in college...

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Feb 15, 2005 11:09 pm

Can you describe in more detail how you relax edges?

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue Feb 15, 2005 11:12 pm

Oh. Haha! I should have READ your test case instead of just running my program on it. I find the path from t to s, so that in the end, my parent[] array contains the path in the right order (from s to t), and on your case this works fine. Of course, if I reverse s and t.... Thanks, Adrian.
If only I had as much free time as I did in college...

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Mon Feb 21, 2005 2:10 pm

Hehe, do you guys like this problem? It is one of my favourite problems in our problemset. I find it quite interesting that many of you use different graph algorithms to solve this task - Dijkstra, Floyd, BFS, Bellman-Ford and even Kruskal & Prim!! 8) 8)

And that's exactly what we desire. The time limit of this task during contest is 5 seconds, so various algorithms could get within time limit. We really want our contestants to think, not just implementing algorithms taken directly from textbooks and papers. The high (?!) time limit is employed to encourage everyone to try this task... FYI, the judge solution uses Floyd twice, and it runs a bit longer than 1 second.

Hope to see your opinions towards this task. :wink:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Demon
New poster
Posts: 1
Joined: Tue Apr 05, 2005 1:14 pm

10816 - Travel in Desert

Post by Demon » Tue Apr 05, 2005 1:36 pm

Hellow
I am getting wrong answer again and again.Can anybody post me more sample I/O.I get correct answer for all the posted sample I/O so far. :cry:

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Mon Apr 11, 2005 3:31 pm

do u explain your approach?

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

Post by artem » Sun Aug 14, 2005 1:47 pm

Check this input:
  • 20 19
    1 11
    1 20 3 3
    20 2 78 34
    2 19 78 3
    19 3 78 3
    3 18 78 5
    18 4 1 23
    4 17 1 23
    17 5 1 1
    5 16 1 1
    16 6 2 23
    6 15 34 3
    15 7 35 3
    7 14 2 23
    14 8 78 3
    8 13 24 2
    13 9 3 34
    9 12 2 1
    12 10 34 3
    10 11 3 34
    20 19
    1 20
    1 2 3 53
    2 3 35 35
    3 4 23 3
    4 5 7 7
    5 6 34 2
    6 7 11 6
    7 8 24 1
    8 9 2 23
    9 10 21 1
    10 11 12 17
    11 12 24 23
    12 13 24 2
    13 14 23 1
    14 15 1 5
    15 16 1 19
    16 17 25 23
    17 18 30 30
    18 19 2 2
    19 20 4 7
    3 4
    1 3
    1 2 1 3
    1 2 3 1
    1 2 2 2
    2 3 2 2
My AC program give this output:
  • 1 20 2 19 3 18 4 17 5 16 6 15 7 14 8 13 9 12 10 11
    225.0 78.0
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    260.0 35.0
    1 2 3
    4.0 2.0

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Tue Aug 16, 2005 8:34 am

artem wrote:Check this input:

Code: Select all

20 19
1 11 
1 20 3 3
20 2 78 34
2 19 78 3
19 3 78 3
3 18 78 5
18 4 1 23
    ^^^
...
Your input is not correct
problem description wrote:... Each line contains 2 integers X, Y and 2 real numbers R and D (1 ≤ X, Y ≤ N; 20 ≤ R ≤ 50; 0 < D ≤ 40).
R should be at least 20...

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

Post by artem » Tue Aug 16, 2005 5:40 pm

Yes, you is right, but AC program must gives for this input right output.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Tue Aug 16, 2005 8:42 pm

Yes, you are probably right that many ACs will give right outputs for such inputs, too. But somebody's solution may rely on the conditions given in the problem statement and so become confused why his solution gives wrong outputs for these inputs.

There is one more condition your inputs don't follow: (and actually my solution was relying on it :wink: )
problem statement wrote:Each real number has exactly one digit after the decimal point.
Nevertheless, the outputs are correct :D .

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

10816 - Help plz

Post by mamun » Thu Oct 27, 2005 1:17 am

There might be more than one path between a pair of oases.
I understand, that means there will be more than a pair of temperature and distance between the intermediate oasis (direct path). If that is the case then how do we handle that? Do we discard all but the lowest temperature pair?

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Oct 29, 2005 7:48 pm

Hi,
To decide where to go, they will pick a route that the highest temperature is minimized. If more than one route satisfy this criterion, they will choose the shortest one.
So the answer is: it doesn't matter how you deal with the edges, as long as you observe the above requirements. (In some implementations, you don't need to discard any edges at all.)

Check out this topic too:
http://online-judge.uva.es/board/viewtopic.php?t=7527

Have fun!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

10816 Travelling in the desert----- WA hlp plz

Post by shihabrc » Wed Jan 18, 2006 9:17 pm

Hi all,

I've been tryin 2 solve this one with Kruskal(considering temparature as weight) and bellman(considering distance). Is this procedure correct? I'm gettin WA for this. Plz somebody hlp. (Sugg., I/Os ... anything)

Code: Select all

#include<stdio.h>
#include<stdlib.h>
#define INF 999999

typedef struct Edge{
	int u,v;
	double d,t;
} Edge;

Edge edge[10100];
Edge tedge[220];
int v,E,TE;
double d[105];
int set[105];
int pre[105];
double max[105];

void print_path(int,int);
void make_set(void);
void Set_union(int ,int );
void mst(void);
int comp(const void*,const void*);
double Max(double a,double b){
	return a>b?a:b ;
}

void main(void){
	int i,j,m,n,a,b;
	double p,q;
	
	
	while(scanf("%d %d",&v,&E)==2){
		scanf("%d %d",&m,&n);
		
		j=0;
		for(i=0;i<E;i++){
			scanf("%d %d %lf %lf",&a,&b,&p,&q);

			edge[j].u=edge[j+1].v=a;
			edge[j].v=edge[j+1].u=b;
			edge[j].t=edge[j+1].t=p;
			edge[j].d=edge[j+1].d=q;

			j+=2;
		}

		E=j;
	
		qsort(edge,E,sizeof(Edge),comp);

		mst();

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

		for(i=0;i<v-1;i++){
			for(j=0;j<TE;j++){
				if(d[tedge[j].v]>d[tedge[j].u]+tedge[j].d){
					d[tedge[j].v]=d[tedge[j].u]+tedge[j].d;
					max[tedge[j].v]=Max(max[tedge[j].u],tedge[j].t);
					pre[tedge[j].v]=tedge[j].u;
				}
			}
		}
		
		print_path(m,n);
		putchar('\n');
		printf("%.1lf %.1lf\n",d[n],max[n]);

	}
}

int comp(const void* x,const void* y){
	Edge* a=(Edge*) x;
	Edge* b=(Edge*) y;

	if(a->t > b->t) return 1;
	else if(a->t < b->t) return -1;
	else{
		if(a->d > b->d) return 1;
		else if(a->d , b->d) return -1;
		else return 0;
	}
}

void make_set(void){
	int i;

	for(i=1;i<=v;i++) set[i]=i;
}

void Set_union(int a,int b){
	int i,j=set[b];

	for(i=1;i<=v;i++){
		if(set[i]==j) set[i]=set[a];
	}
}

void mst(void){
	int i,j;

	make_set();
	j=0;

	for(i=0;i<E;i++){
		if(set[edge[i].u]!=set[edge[i].v]){
			tedge[j].u=tedge[j+1].v=edge[i].u;
			tedge[j].v=tedge[j+1].u=edge[i].v;
			tedge[j].t=tedge[j+1].t=edge[i].t;
			tedge[j].d=tedge[j+1].d=edge[i].d;
			Set_union(edge[i].u,edge[i].v);
			j+=2;
		}
	}

	TE=j;
}

void print_path(int i,int j){
	if(i==j) printf("%d",i);
	else print_path(i,pre[j]);
	if(i!=j) printf(" %d",j);
}
-Shihab
Shihab
CSE,BUET

Post Reply

Return to “Volume 108 (10800-10899)”