10816 - Travel in Desert

[Abednego]

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.

[Adrian Kuegel]

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

[Abednego]

Yes, I get the right answer on all the posted test cases.

[Adrian Kuegel]

Can you describe in more detail how you relax edges?

[Abednego]

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.

[Observer]

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.

[Demon]

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]

do u explain your approach?

[artem]

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]

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

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

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

[Martin Macko]

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 )

Each real number has exactly one digit after the decimal point.

Nevertheless, the outputs are correct .

[mamun]

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]

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!

[shihabrc]

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