## 10816 - Travel in Desert

Moderator: Board moderators

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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.

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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Can you describe in more detail how you relax edges?

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

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. L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Contact:

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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
^^^
...
``````
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
Yes, you is right, but AC program must gives for this input right output.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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 )
problem statement wrote:Each real number has exactly one digit after the decimal point.
Nevertheless, the outputs are correct .

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

### 10816 - Help plz

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

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;
Edge tedge;
int v,E,TE;
double d;
int set;
int pre;
double max;

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