10986 - Sending email

[blazej]

Can anyone tell me what can be the reason for getting whole the time TLE on this problem? I am using Dijskra's algorithm, and I don't think this problem can be solved faster...
Are there some "tricks" about reading the input?

I wiil be grateful for any help.

[Renat]

Do you use heap?

[blazej]

yes...
I've tried STL priority_queue, and as well mine heap...

[Abednego]

The input is quite large, so you should use scanf() instead of cin>> to read input.

[blazej]

I'm using <cstdio>...

[Renat]

Then it's probably some error in your code. I've accepted this task with both STL and mine priority queues.

[Adrian Kuegel]

Are you stopping your dijkstra when you take node T out of the priority_queue? This does not improve the worst case complexity, but it improves the runtime on random test cases and can be quite an important optimization.

[blazej]

I finally got ACC. Renat was right, I couldn't find such a stupid bug...
So I'm sorry taking your time, but I have been working on this problem since saturday contest, so I decided to ask start this topic...
Adrian Kuegel - now my program doesn't do it, and it gets ACC at least

[Observer]

Hi,

Please try this code on the judge:

Code: Select all

var f, p, c, n, m, s, t, i, j, k : longint;
begin
  readln(c);
  for p := 1 to c do begin
    readln(n, m, s, t);
    while m >= 50000 do write;
    for f := 1 to m do readln(i, j, k);
  end;
end.

This code gives TLE. That could mean that the test data is incorrect (may contain m >= 50000).

I might be wrong, but since I'm getting WA I'm trying everything I can think of...

Thanks for your attention.

[Abednego]

Oops. A small mistake. There are test cases with m = 50000.
There are no test cases with m > 50000.

[Observer]

Hi,

Yes you are right. Changing >= into > would get rid of TLE (WA in < 1 sec.). And the same thing happens to n (n can be equal to 20000).

I have also tried this:

Code: Select all

var f, p, c, n, m, s, t, i, j, w : longint; 
begin 
  readln(c); 
  for p := 1 to c do begin 
    readln(n, m, s, t); 
    for f := 1 to m do begin
      readln(i, j, w); 
      while w > 10000 do write;
    end;
  end; 
end.

And this gives TLE as well, so... maybe we have some w > 10000?..... But since so many people have got this problem accepted (including PASCAL submissions) the mistake may be on my side...

Thanks again.

[Ahmed_Hasan]

I think there is nothing to do with the algorithm to make the solution faster. Because everybody talked here tried or solved it with dijkstra. But i m getting TLE for my dijkstra. So I m giving my dijkstra code here so that anybody can give me any hint to make my code faster.

Code: Select all

#include<cstdio>
#include<list>
#include<queue>
using namespace std;

#define maxv 20010
#define INF 999999999

struct node{int v,cost;};

list<node> G[maxv];	
int D[maxv];
int V,E,S,T;

//*************************Dijkstra*************************//
class Qele				//Q elements
{ 
	public: int v; 
	bool operator<(const Qele &t)const{	return D[t.v]<D[v];}
};
void Dijkstra(int s)
{
	int c1,v;
   Qele A[maxv];
	for(c1=0;c1<V;c1++) D[c1]=INF;
	for(c1=0;c1<V;c1++) A[c1].v=c1;
   D[s]=0;
	list<node>::iterator Adj;

	for(c1=0;c1<V;c1++){
		make_heap(A+c1,A+V);
		v=A[c1].v;
		if(v==T) break;
		for(Adj=G[v].begin();Adj!=G[v].end();Adj++)
			if( D[Adj->v]>D[v]+Adj->cost)
				D[Adj->v]=D[v]+Adj->cost;
    }
}
//*************************Dijkstra*************************//

void Init()
{
	int c1;
	for(c1=0;c1<=V;c1++)
	{
		G[c1].clear();
		D[c1]=INF;
	}

}

int main()
{
	freopen("10986.txt","r",stdin);
	int c1,cas,casc=0,v1,v2,cost;
	node n;
	scanf("%d",&cas);
	for(casc=1;casc<=cas;casc++)
	{
		Init();

		scanf("%d %d %d %d",&V,&E,&S,&T);
		for(c1=0;c1<E;c1++)
		{
			scanf("%d %d %d ",&v1,&v2,&cost);

			n.cost=cost;
			n.v=v2;
			G[v1].push_back(n);
			n.v=v1;
			G[v2].push_back(n);
		}

		Dijkstra(S);
		if(D[T]==INF)
			printf("Case #%d: unreachable\n",casc);
		else
			printf("Case #%d: %d\n",casc,D[T]);

	}
	return 0;
}

[Abednego]

Your algorithm runs in n^2 time. In your Dijkstra() function, for each vertex, you run make_heap().

make_heap() takes linear time.

[Ahmed_Hasan]

Thanks Abednego. It was really an important information about the make_heap(). I think STL should not be like this, it should work in the best way. Whatever, now I use priority Q and got AC.

[Abednego]

How could you possibly write make_heap() so that it would run in faster than linear time?! make_heap() _creates_ a heap. it doesn't modify an existing heap. To create a heap, you have to read the whole given array, and that takes linear time.