10986 - Sending email

[nymo]

To asif_rahman0, thanks, but, shouldn't the output for third case be 11? [path 5 -> 4 -> 3 -> 1 -> 2]

[asif_rahman0]

Sorry that was typo.

[nymo]

Some more test cases please... so that I can figure out the error.

[asif_rahman0]

If you post your code then it will be easy for me to figure out your error.

[nymo]

To asif_rahman0, I 've sent you a PM.

EDIT: THANKS TO asif_rahman0, HE FOUND A SMALL ERROR IN MY CODE. NOW I GET ACCEPTED. THANKS AGAIN.

[898989]

Hi, I am suffering much to get AC in this problem. I already got AC with that code[Dijkstra+heap] before @ usaco. I wish if any one can help.

Code: Select all

Cut after AC. Small OO caused WA

[newton]

What was your problem?

[898989]

Thx so much.
I discovered my bug.

[bishop]

thanx mf
got AC

[mf]

My gcc produces these errors:

Code: Select all

p.cc:12: error: ‘std::list<one, std::allocator<one> > link [20002]’ redeclared as different kind of symbol
/usr/include/unistd.h:757: error: previous declaration of ‘int link(const char*, const char*)’
p.cc: In function ‘void Free()’:
p.cc:33: error: pointer to a function used in arithmetic
p.cc:33: error: request for member ‘clear’ in ‘*(((int (*)(const char*, const char*)throw ())((unsigned int)m)) + link)’, which is of non-class type ‘int ()(const char*, const char*)throw ()’
p.cc: In function ‘int Dijkstra(int, int)’:
p.cc:52: error: pointer to a function used in arithmetic
p.cc:52: error: request for member ‘begin’ in ‘*(((int (*)(const char*, const char*)throw ())((unsigned int)s.two::node)) + link)’, which is of non-class type ‘int ()(const char*, const char*)throw ()’
p.cc:52: error: pointer to a function used in arithmetic
p.cc:52: error: request for member ‘end’ in ‘*(((int (*)(const char*, const char*)throw ())((unsigned int)s.two::node)) + link)’, which is of non-class type ‘int ()(const char*, const char*)throw ()’
p.cc: In function ‘int main()’:
p.cc:81: error: pointer to a function used in arithmetic
p.cc:81: error: request for member ‘push_back’ in ‘*(((int (*)(const char*, const char*)throw ())((unsigned int)v)) + link)’, which is of non-class type ‘int ()(const char*, const char*)throw ()’
p.cc:83: error: pointer to a function used in arithmetic
p.cc:83: error: request for member ‘push_back’ in ‘*(((int (*)(const char*, const char*)throw ())((unsigned int)u)) + link)’, which is of non-class type ‘int ()(const char*, const char*)throw ()’

Choose a different name for symbol 'link', or put it in a separate namespace - preventing this kind of naming conflicts is exactly the reason why namespaces exist.

[TiagoTC]

Could someone help me with my code? I think there is something wrong with memory (I'm getting Runtime Error). There is my code:

Code: Select all

#include <cstdio>

#include <queue>
#include <climits>
#include <vector>

using namespace std;

//const int MAX_V = 2000;
//const int MAX_ARESTAS = 5001;

//const int INF = INT_MAX;

const int MAX_V = 20001;

const int MAX_EDGES = 50001;

const int INF = INT_MAX;

typedef struct grafo

{

        int v, w;

}GRAPH;

int N, n, m, S, T;

int degree[MAX_V], dist[MAX_V], f[MAX_V];//f: father

vector< vector<GRAPH> > g(MAX_V, vector<GRAPH>(MAX_EDGES));


//GRAFO g[MAX_V][MAX_ARESTAS];


void Inic()

{

     for(int i=0; i<n; i++){

             degree[i] = 0;

     }

}

pair<int, int> MP(int v, int w)

{

    pair<int, int> P;

    P.first = v;     P.second = w;



    return P;    

}

void dijkstra(int o, int dest)//o: source

{

    priority_queue< pair<int, int> > heap;//w, vertice

    int s, t, w;



    for(int i=0; i<n; i++){

        dist[i] = INF;

        f[i] = i;

    }

    heap.push( MP(dist[o]=0, o) );



    while(!heap.empty()){

        s = heap.top().second;

        heap.pop();



        for(int i=1; i<=degree[s]; i++){

            t = g[s][i].v;

            w = g[s][i].w;

            if(dist[s] + w < dist[t]){

                dist[t] = dist[s] + w;

                f[t] = s;

                heap.push(  MP(-dist[t], t) );

            }

        }

        

        if(s == dest) return;//Optimization

    }

}

int main()
{
	scanf("%d", &N);
	for(int test=1; test<=N; test++){
		scanf("%d %d %d %d", &n, &m, &S, &T);

		Inic();

		for(int M=1; M<=m; M++){
			int s, d, w;
			scanf("%d %d %d", &s, &d, &w);

			degree[s]++; degree[d]++;


                    	g[s][ degree[s] ].v = d;

                    	g[s][ degree[s] ].w = w;

			g[d][ degree[d] ].v = s;

                    	g[d][ degree[d] ].w = w;
		}

		dijkstra(S, T);

		printf("Case %d#: ", test);
		if(dist[T] == INF) printf("unreachable\n");
		else printf("%d\n", dist[T]);
	}
}

Thank you in advance.

[neilor]

Hello People.

Follow some test cases to the problem (test using uva tookit: http://uvatoolkit.com/problemssolve.php)
75

6 3 0 2
0 1 50
2 1 70
0 2 150

2 1 0 1
1 0 33333

2 0 0 0

2 1 0 1
1 0 111

2 2 0 1
1 0 100
0 1 33

2 1 0 1
0 1 100
3 3 2 0
0 1 100
0 2 200
1 2 50
2 0 0 1



14 20 13 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
8 2 575
9 4 235
2 8 437
9 12 367
13 7 587
11 9 476
9 5 34
11 13 35
13 10 2
12 11 7
12 6 235

14 16 11 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
9 4 235
9 12 367
13 7 587
11 9 476
9 5 34
13 11 2
12 11 7

4 5 0 3
0 2 17
0 3 18
2 3 11
2 1 2
0 1 4

4 7 0 3
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

4 7 2 1
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 4
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

14 20 13 2
0 1 123
1 2 4567
2 3 4578
4 5 5678
5 3 47
2 6 256
7 2 2346
5 9 2345
5 3 12345
8 2 5785
9 4 2345
2 8 4367
9 12 3467
13 7 5687
11 9 4576
9 5 34
11 13 345
13 11 2
12 11 7
12 6 235898

14 20 13 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
8 2 575
9 4 235
2 8 437
9 12 367
13 7 587
11 9 476
9 5 34
11 13 35
13 10 2
12 11 7
12 6 235

14 16 11 2
0 1 123
1 2 467
2 3 478
4 5 578
5 3 47
2 6 256
7 2 246
5 9 245
5 3 1245
9 4 235
9 12 367
13 7 587
11 9 476
9 5 34
13 11 2
12 11 7


6 7 0 4
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 3 0
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 2
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 1
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 0 0
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 1 2
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4

6 7 2 3
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4


5 5 0 4
0 1 3
1 0 2
1 0 1
0 1 4
1 4 1000

6 9 5 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 3 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 4 3
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 5 5
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 13 0 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 1 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 2 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 3 4
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 13 2 5
0 1 14
0 2 17
1 0 11
0 3 18
2 3 11
2 1 2
0 1 4
0 2 7
1 0 1
0 3 8
2 3 1
2 1 2
5 3 100

6 9 0 5
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 5 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 3 0
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

8 7 4 6
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

1 1 0 0
0 0 25

5 4 0 4
1 2 404
3 4 505
3 2 606
1 0 100

6 7 5 0
2 3 404
4 5 505
3 5 606
4 3 303
1 2 100
0 4 201
1 5 707

4 3 0 2
0 1 50
2 1 70
0 2 150

4 3 1 2
0 1 50
2 1 70
0 2 150

6 9 5 0
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 0 5
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 5 2
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

6 9 3 0
0 1 4
0 2 2
1 2 1
1 3 5
2 3 8
2 4 10
3 4 2
3 5 6
4 5 3

8 7 4 6
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 6 4
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 2 5
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 2 6
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 2 7
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 3 7
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 0 7
4 3 404
2 3 505
1 2 606
0 1 303
4 5 100
5 6 201
6 7 707

8 7 0 7
0 1 404
1 2 505
2 3 606
3 4 303
4 5 100
5 6 201
6 7 707

8 7 0 7
0 1 404
3 2 505
2 1 606
5 6 303
4 5 100
3 4 201
6 7 707

8 7 0 7
4 3 404
4 5 505
5 6 606
3 2 303
2 1 100
6 7 201
0 1 707

8 7 0 7
1 2 404
6 7 505
3 4 606
0 1 303
5 4 100
5 6 201
3 2 707

8 7 3 7
3 2 404
2 1 505
1 0 606
0 4 303
4 5 100
5 6 201
6 7 707

8 7 3 7
2 3 404
1 2 505
0 1 606
4 0 303
5 4 100
6 5 201
6 7 707

1 1 0 0
0 0 25

5 4 0 4
1 2 404
3 4 505
3 2 606
1 0 100

6 7 0 5
2 3 404
4 5 505
3 5 606
4 3 303
1 2 100
0 4 201
1 5 707

6 3 0 2
0 1 50
2 1 70
0 2 150


2 1 0 1
1 0 33333

2 1 0 2
0 2 103

2 0 0 1

2 0 1 2

4 3 0 3
2 0 50
1 2 70
3 1 150

2 1 0 1
0 1 100

3 3 2 0
0 1 100
0 2 200
1 2 50

4 3 0 3
2 0 50
1 2 70
3 1 150

2 1 0 1
0 1 100

3 3 2 0
0 1 102
0 2 202
1 2 52

4 3 1 0
1 2 104
2 3 204
0 3 54

[neilor]

Dears.

Forget dijkstra and heap, make heap, etc. I have implemented with some variances:
1 - Dijkstra with dinamic list (TLE) (using only #include <cstdio>)
2 - Dijkstra with STL make_heap (TLE)
3 - Dijkstra with heap (like recomended here using only #include <cstdio>)
Accepted: tempo: 0.580 (2 days of work)

Try:
4 - BellmanFord (using only #include <cstdio>) http://en.wikipedia.org/wiki/Bellman-Ford_algorithm
Accepted: tempo: 0.880 (10 minutes of work)

best regards,
Neilor Tonin (nat@uri.com.br)

[aliahmed]

Cut after Accepted...

[Mehadi]

please help me......
Why I have got TLE, can't understand

Code: Select all

#include<iostream>
#include<vector>
#define inf 1000000000
#define SIZE1 20000
#define SIZE2 50000
using namespace std;

typedef vector<int>graph;
long Q[SIZE1+9],d[SIZE1+9];

graph G[SIZE2*2+9],W[SIZE2*2+9];

//min_heapify with respect to d[]
long min_heapify(long i,long n)
{
	long temp,minimum,l,r;
	l=2*i;
	r=2*i+1;
	if(l<=n && d[Q[l]]<d[Q[i]])
		minimum=l;
	else
		minimum=i;
	if(r<=n && d[Q[r]]<d[Q[minimum]])
		minimum=r;
	if(minimum!=i)
	{
		temp=Q[i];
		Q[i]=Q[minimum];
		Q[minimum]=temp;
		min_heapify(minimum,n);
	}
	return 0;
}
long build_min_heap(long n)
{
	long i;
	for(i=n/2;i>0;i--)
	{
		min_heapify(i,n);
	}
	return 0;
}
long extract_min_Q(long n)
{
	build_min_heap(n);
	long min;
	min=Q[1];
	Q[1]=Q[n];
	return min;
}
int main()
{
	long i,j,n,m,u,v,w,source,dest,t;	
	scanf("%ld",&t);
	for(j=1;j<=t;j++)
	{
		scanf("%ld%ld%ld%ld",&n,&m,&source,&dest);
		for(i=1;i<=n;i++)
		{
			G[i].clear();
			W[i].clear();
		}
		for(i=1;i<=m;i++)
		{
			scanf("%ld%ld%ld",&u,&v,&w);			
			G[u+1].push_back(v+1);
			G[v+1].push_back(u+1);
			W[u+1].push_back(w);
			W[v+1].push_back(w);
		}
		for(i=1;i<=n;i++)
		{
			d[i]=inf;
			Q[i]=i;
		}
		d[source+1]=0;		
		while(n>0)
		{
			u=extract_min_Q(n);
			n--;
			for(v=0;v<G[u].size();v++)
			{
				if((d[u]+W[u][v])<d[G[u][v]])
				{
					d[G[u][v]]=d[u]+W[u][v];
				}
			}			
		}
		if(d[dest+1]==inf)
			printf("Case #%ld: unreachable\n",j);
		else
			printf("Case #%ld: %ld\n",j,d[dest+1]);
	}
	return 0;
}