10986 - Sending email

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

avdtech
New poster
Posts: 3
Joined: Wed Jan 05, 2011 11:15 pm

Re: 10986 - Sending email

Post by avdtech » Sat Mar 19, 2011 7:26 am

Just a little correction in the test cases posted by neilor -

TC#66 is wrong -

it should be
3 1 0 2
0 2 103

instead of
2 1 0 2
0 2 103

since the nodes are number from 0 to n-1.

Thanks for the cases. It helped a lot.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10986 - Sending email

Post by DD » Sat Mar 26, 2011 6:59 pm

neilor wrote:Hello People.

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

Code: Select all

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
Thank you for providing the test case :lol:
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

LeonardoB
New poster
Posts: 2
Joined: Wed May 11, 2011 3:39 pm

TLE Sending email 10986

Post by LeonardoB » Tue Jun 07, 2011 6:51 pm

Hi.

I got tle in this problem using Dijkstra algorithm and priority queu.

Code: Select all

include <cstdlib>
#include <string>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <map>
#include <list>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <limits>
#include <cctype>
#include <queue>

using namespace std;

class Graph {

private:
	struct Node;

	class compare {

	private:
		int * dist;

	public:
		compare (int * d) : dist(d) {}
		bool operator () (const Node* n1, const Node* n2) {

			return dist[n1->id] < dist[n2->id];
		}
	};

	struct Edge {

		Node * begin, * end;
		int value;
		friend bool operator < (const Edge & e1, const Edge & e2) {
			return e1.value < e2.value;
		}
	};

	struct Node {
		
	public:
		
		int id;
		vector<Edge> next;
		bool visited;
	};

	Node* nodes;
	int* dist;
	int N;

public:
	
	Graph (int k) {
		N = k;
		nodes = new Node[k + 1];
		dist = new int[k + 1];

		for (size_t i = 0; i < k + 1; ++i)
			nodes[i].visited = false;
	}

	~Graph() {

		delete [] dist;
		delete [] nodes;
	}

	void add_node (int from, int to, int value) {
		nodes[from].id = from;
		nodes[to].id = to;

		Edge e = { &nodes[from], &nodes[to], value };
		nodes[from].next.push_back (e);
	}

	int dijkstra (int from, int to) {

		memset (dist, 0x3F3F3F3F, sizeof (int) * (N + 1));

		const compare c1 (dist);
		priority_queue<Node*, deque<Node*>, compare> q (c1);

		dist[from] = 0; 
		
		q.push (&nodes[from]);
		

		while (!q.empty()) {
			Node* t = q.top();
			q.pop();

			for (vector<Edge>::iterator it = t->next.begin(); it != t->next.end(); ++it) {

				it->end->visited = true;
				dist[it->end->id] = min (dist[it->end->id], dist[t->id] + it->value);

				q.push (it->end);
			}
		}

		return nodes[to].visited ? dist[to] : -1;
	}

};

int main() {

	int K, N, M, S, T, A, B, V;

	scanf ("%d", &K);

	for (size_t k = 0; k < K; ++k) {

		scanf ("%d %d %d %d", &N, &M, &S, &T);

		Graph g (N);

		for (size_t m = 0; m < M; ++m) {
			scanf ("%d %d %d", &A, &B, &V);
			g.add_node (A, B, V);
		}

		int out = g.dijkstra (min (S, T), max (S, T));

		if (out == -1) printf ("Case #%d: unreachable\n", k + 1);
		else printf ("Case #%d: %d\n", k + 1, out);

	}

	return 0;
}

JohnsonWang
New poster
Posts: 4
Joined: Wed May 11, 2011 6:14 am

Re: 10986 - Sending email

Post by JohnsonWang » Thu Jul 07, 2011 1:10 am

Hi All,

I'm having a similar issue - my submission is returning a TLE, however, it seems to work on all my local test cases just fine. I'm using a simple Dijkstra's, without any real optimisations.

Here is the code:

Code: Select all

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

const int INF = 9e8;

int get_min_dist( int starting_node, int ending_node, map < int, vector < pair <int, int> > > adj_list, int num_nodes )
{
	vector <int> distances( num_nodes, INF );
	distances[starting_node] = 0;

	priority_queue < pair <int, int> > pq;
	pq.push( make_pair( starting_node, 0 ) );

	while( !pq.empty() )
	{
		pair <int, int> cur = pq.top();
		pq.pop();
	
		vector < pair <int, int> >::iterator it = adj_list[cur.first].begin();
		while( it != adj_list[cur.first].end() )
		{
			if( distances[it->first] > distances[cur.first] + it->second )
			{
				distances[it->first] = distances[cur.first] + it->second;
				pq.push( make_pair( it->first, distances[it->first] ) );
			}
			it++;
		}
	}

	return distances[ending_node];
}

int main()
{
	int num_test_cases;
	cin >> num_test_cases;

	for( int test_case_no = 1; test_case_no <= num_test_cases; test_case_no++ )
	{
		int num_nodes, num_edges, starting_node, ending_node;
		cin >> num_nodes >> num_edges >> starting_node >> ending_node;

		map < int, vector < pair <int, int> > > adj_list;
		for( int edge_no = 0; edge_no < num_edges; edge_no++ )
		{
			int from, to, cost;
			cin >> from >> to >> cost;
			adj_list[from].push_back( make_pair( to, cost ) );
			adj_list[to].push_back( make_pair( from, cost ) );
		}
	
		cout << "Case #" << test_case_no << ": ";
		int dist = get_min_dist( starting_node, ending_node, adj_list, num_nodes );
		if( dist == INF ) cout << "unreachable" << endl;
		else cout << dist << endl;
	}

	return 0;
}

shanto_0321
New poster
Posts: 4
Joined: Sun Sep 11, 2011 8:12 am

Re: 10986 - Sending email

Post by shanto_0321 » Sun Sep 11, 2011 3:01 pm

if we scan a='0',then why we do not get the value of a=48-'0'=0.
what is the problem.

Code: Select all

#include<stdio.h>
#include<math.h>
#include<string.h>
int main()
{
char a[23];
int i,s=0,len;
while(scanf("%s",a)!=EOF)
{
printf("%lld",a);
if((a-48)==0)
             break;
            
      else
{
len=strlen(a);
i=0;
while(a[i]!='\0')
           {          
           s=s+(a[i]-48)*(pow(2,(len))-1);
           i++;
           len--;
           }
printf("%lld",s);
printf("\n");
s=0;
}
}
return 0;
}

pranon
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

Re: 10986 - Sending email

Post by pranon » Sun Jul 29, 2012 7:29 pm

Is there something I can do to make my code more efficient? Or does it fall in an infinite loop for some test case?
Any pointers as to how the code can be made more efficient?
Thanks in advance :'(

Code: Select all

Code Edited
Last edited by pranon on Wed Aug 01, 2012 10:32 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10986 - Sending email

Post by brianfry713 » Tue Jul 31, 2012 12:11 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

pranon
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

Re: 10986 - Sending email

Post by pranon » Tue Jul 31, 2012 8:12 am

Ok, I'm extremely sorry I posted without removing the...
Ok, here's the code. getting ``Time Limit Exceeded".

Code: Select all

#include <stdio.h>
#include <string.h>

void djikstra(int i);
void insert(int i);
int pop(void);
void update(int i);
void initialize(void);
int adj[20003][20003], weight[20003][20003], dis[20003], iindex[20003], heap[20003], n, des, end=1, apoc;
char seen[20003];


int main()
{
    int t, m, source, a, b, w;
    register int x;
    scanf("%d", &t);
    for(x=1; x<=t; x++)
    {
        scanf("%d %d %d %d", &n, &m, &source, &des);
        apoc=n;
        if(x>1)
            initialize();
        while(m--)
        {
            scanf("%d %d %d", &a, &b, &w);
            adj[a][0]++;
            adj[b][0]++;
            weight[a][adj[a][0]]=w;
            weight[b][adj[b][0]]=w;
            adj[a][adj[a][0]]=b;
            adj[b][adj[b][0]]=a;
        }
        djikstra(source);
        printf("Case %c%d: ", '#', x);
        seen[des]==2?printf("%d\n", dis[des]):printf("unreachable\n");
        /*for(i=0; i<n; i++)
            if(seen[i]!=0)
                printf("i= %d, dis = %d\n", i, dis[i]);*/
    }
    return 0;
}

void djikstra(int source)
{
    int i, small;
    seen[source]=1;
    dis[source]=0;
    insert(source);
    while(apoc)
    {
        small=pop();
        apoc--;
        seen[small]=2;
        if(small==des)
            break;
        for(i=1; i<=adj[small][0]; i++)
            if(seen[adj[small][i]]!=2)
            {
                if(seen[adj[small][i]]==0)
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    insert(adj[small][i]);
                    seen[adj[small][i]]=1;
                }
                else if(dis[adj[small][i]]>dis[small]+weight[small][i])
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    update(adj[small][i]);
                }
            }
    }
    return;
}

void insert(int i)
{
    int cur=end, par=end>>1, temp;
    heap[end]=i;
    end++;
    while(par>=1 && dis[heap[par]]>dis[heap[cur]])
    {
        temp=heap[par];
        heap[par]=heap[cur];
        heap[cur]=temp;
        iindex[heap[cur]]=cur;
        cur=par;
        par>>=1;
    }
    iindex[heap[cur]]=cur;
    /*for(i=1; i<end; i++)
        printf("%d\n", heap[i]);*/
    return;
}

int pop(void)
{
    int node, even, odd, cur, min, temp;
    end--;
    node=heap[1];
    heap[1]=heap[end];
    iindex[heap[1]]=1;
    cur=1;
    even=2, odd=3;
    while(odd<end && (dis[heap[cur]]>dis[heap[even]] || dis[heap[cur]]>dis[heap[odd]]))
    {
        min=dis[heap[odd]]>dis[heap[even]]?even:odd;
        temp=heap[min];
        heap[min]=heap[cur];
        heap[cur]=temp;
        iindex[heap[min]]=min;
        iindex[heap[cur]]=cur;
        cur= min;
        even=cur<<1;
        odd=even+1;
    }
    /*for(i=1; i<end; i++)
        printf("%d\n", heap[i]);*/
    return node;
}

void update(int node)
{
    int i, m, temp;
    i=iindex[node];
    m=i>>1;
    while(m>=1 && dis[heap[i]]<dis[heap[m]])
    {
        temp=heap[m];
        heap[m]=heap[i];
        heap[i]=temp;
        iindex[heap[i]]=i;
        i=m;
        m>>=1;
    }
    iindex[node]=i;
    /*for(i=1; i<end; i++)
        printf("%d\n", heap[i]);*/
    return;
}

void initialize(void)
{
    int i;
    for(i=0; i<n; i++)
        adj[i][0]=0;
    memset(seen, 0, n*sizeof(char));
    end=1;
    return;
}

Thanks in advance.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10986 - Sending email

Post by brianfry713 » Wed Aug 01, 2012 3:42 am

I used a C++ STL priority_queue in Dijkstra's algorithm. Is your queue logarithmic?
Check input and AC output for thousands of problems on uDebug!

pranon
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

Re: 10986 - Sending email

Post by pranon » Wed Aug 01, 2012 8:26 am

Yes, I think it takes lg(n) operations to insert, pop and update some node in the worst case. It's an array stored like a heap.
I don't know stl. :(
I edited my code after getting accepted in 929. But still ``Time Limit Exceeded".

Code: Select all

#include <stdio.h>
#include <string.h>

void djikstra(int i);
void insert(int i);
int pop(void);
void update(int i);
void initialize(void);
int adj[20003][20003], weight[20003][20003], dis[20003], iindex[20003], heap[20003], n, des, end=1, apoc;
char seen[20003];


int main()
{
    int t, m, source, a, b, w;
    register int x;
    scanf("%d", &t);
    for(x=1; x<=t; x++)
    {
        scanf("%d %d %d %d", &n, &m, &source, &des);
        apoc=n;
        if(x>1)
            initialize();
        while(m--)
        {
            scanf("%d %d %d", &a, &b, &w);
            adj[a][0]++;
            adj[b][0]++;
            weight[a][adj[a][0]]=w;
            weight[b][adj[b][0]]=w;
            adj[a][adj[a][0]]=b;
            adj[b][adj[b][0]]=a;
        }
        djikstra(source);
        printf("Case %c%d: ", '#', x);
        seen[des]==2?printf("%d\n", dis[des]):printf("unreachable\n");
    }
    return 0;
}

void djikstra(int source)
{
    int i, small;
    seen[source]=1;
    dis[source]=0;
    insert(source);
    while(apoc)
    {
        small=pop();
        apoc--;
        seen[small]=2;
        if(small==des)
            break;
        for(i=1; i<=adj[small][0]; i++)
            if(seen[adj[small][i]]!=2)
            {
                if(seen[adj[small][i]]==0)
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    insert(adj[small][i]);
                    seen[adj[small][i]]=1;
                }
                else if(dis[adj[small][i]]>dis[small]+weight[small][i])
                {
                    dis[adj[small][i]]= dis[small]+weight[small][i];
                    update(adj[small][i]);
                }
            }
    }
    return;
}

void insert(int i)
{
    int cur=end, par=end>>1, temp;
    heap[end]=i;
    end++;
    while(par>=1 && dis[heap[par]]>dis[heap[cur]])
    {
        temp=heap[par];
        heap[par]=heap[cur];
        heap[cur]=temp;
        iindex[heap[cur]]=cur;
        cur=par;
        par>>=1;
    }
    iindex[heap[cur]]=cur;
    return;
}

int pop(void)
{
    int node, even, odd, cur, min, temp;
    end--;
    node=heap[1];
    heap[1]=heap[end];
    iindex[heap[1]]=1;
    cur=1;
    even=2, odd=3;
    while((odd<end || even<end) && (dis[heap[cur]]>dis[heap[even]] || dis[heap[cur]]>dis[heap[odd]]))
    {
        if(odd<end)
            min=dis[heap[odd]]>dis[heap[even]]?even:odd;
        else
            min=dis[heap[even]]<dis[heap[cur]]?even:cur;
        if(min!=cur)
        {
            temp=heap[min];
            heap[min]=heap[cur];
            heap[cur]=temp;
            iindex[heap[min]]=min;
            iindex[heap[cur]]=cur;
        }
        cur= min;
        even=cur<<1;
        odd=even+1;
    }
    return node;
}

void update(int node)
{
    int i, m, temp;
    i=iindex[node];
    m=i>>1;
    while(m>=1 && dis[heap[i]]<dis[heap[m]])
    {
        temp=heap[m];
        heap[m]=heap[i];
        heap[i]=temp;
        iindex[heap[i]]=i;
        i=m;
        m>>=1;
    }
    iindex[node]=i;
    return;
}

void initialize(void)
{
    int i;
    for(i=0; i<n; i++)
        adj[i][0]=0;
    memset(seen, 0, n*sizeof(char));
    end=1;
    return;
}


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10986 - Sending email

Post by brianfry713 » Thu Aug 02, 2012 12:00 am

I think your priority queue must be too slow, my code gets AC in 0.22 seconds. If you can't figure out the C++ STL version try using a different implementation. My code doesn't update the queue when a shorter distance to a node is found, it just pushes another item onto the queue.
Check input and AC output for thousands of problems on uDebug!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10986 - Sending email

Post by mahade hasan » Mon Aug 06, 2012 12:27 am

cut after AC.....
we r surrounded by happiness
need eyes to feel it!

setu basak
New poster
Posts: 4
Joined: Sun Aug 04, 2013 8:35 am

Re: 10986 - Sending email

Post by setu basak » Sun Aug 04, 2013 10:08 am

Code: Select all

#include<bits/stdc++.h>
using namespace std;
vector<int>g[20005];
int cost[20005][20005];
int d[20005];
struct node
{
    int u,w;
    node(int a,int b)
    {
        u=a;w=b;
    }
    bool operator < (const node& p)const
    {
        return w>p.w;
    }
};
void reset()
{
    for(int i=0;i<20005;i++)
        g[i].clear();
}
int dijkstra(int n,int src,int des)
{
    memset(d,63,sizeof(d));
    priority_queue<node>q;
    q.push(node(src,0));
    d[src]=0;
    while(!q.empty())
    {
        node top=q.top();
        q.pop();
        int u=top.u;
        if(u==des)
            return d[des];
        for(int i=0;i<g[u].size();i++)
        {
            int v=g[u][i];
            if(d[u]+cost[u][v]<d[v])
            {
                d[v]=d[u]+cost[u][v];
                q.push(node(v,d[v]));
            }
        }
    }
    return -1;

}
int main()
{
    int t,edge_number,src,des,cas=1,u,v,delay,n;
    scanf("%d",&t);
    while(t--)
    {
        reset();
        scanf("%d %d %d %d",&n,&edge_number,&src,&des);
        for(int i=0;i<edge_number;i++)
        {
            scanf("%d %d %d",&u,&v,&delay);
            g[u].push_back(v);
            g[v].push_back(u);
            cost[u][v]=delay;
            cost[v][u]=delay;
        }
        int ret=dijkstra(n,src,des);
        if(ret==-1)
            printf("Case #%d: unreachable\n",cas);
        else
            printf("Case #%d: %d\n",cas,ret);
        cas++;
    }
}

setu basak
New poster
Posts: 4
Joined: Sun Aug 04, 2013 8:35 am

Re: 10986 - Sending email

Post by setu basak » Sun Aug 04, 2013 10:11 am

above code give me TLE ..couldn't understand..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10986 - Sending email

Post by brianfry713 » Tue Aug 06, 2013 4:01 am

I made a few optimizations to your code and got it AC in 1.6 seconds. Change reset to only clear g[0] through g[n - 1]. In dijkstra, only set d[0] through d[n - 1] to infinity.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 109 (10900-10999)”