10816 - Travel in Desert
Moderator: Board moderators
-
- 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.
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).
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.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- 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...
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.


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
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
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.
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.

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
- 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
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Your input is not correctartem 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 ^^^ ...
R should be at least 20...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).
-
- 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
)
.
There is one more condition your inputs don't follow: (and actually my solution was relying on it

Nevertheless, the outputs are correctproblem statement wrote:Each real number has exactly one digit after the decimal point.

10816 - Help plz
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?There might be more than one path between a pair of oases.
Hi,
Check out this topic too:
http://online-judge.uva.es/board/viewtopic.php?t=7527
Have fun!
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.)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.
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
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org
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)
-Shihab
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
CSE,BUET
CSE,BUET